X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/e944a6e5c1d0ba117954365dfedad16f183cf681..6c611637ef05c993351fece7ff89ee10a2090031:/hamilton.tex diff --git a/hamilton.tex b/hamilton.tex index 17d9380..b2c6e54 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -1,5 +1,5 @@ Many approaches have been developed to solve the problem of building -a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties +a Gray code in a $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties the produced code has to verify. For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on balanced Gray codes. In the transition sequence of these codes, @@ -16,14 +16,15 @@ and an algorithm that establishes locally balanced Gray codes is given. The current context is to provide a function $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian -cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated +cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated $b$ times to produce a pseudo random number, \textit{i.e.} a vertex in the -$\mathsf{N}$ cube. +$\mathsf{N}$-cube. Obviously, the number of iterations $b$ has to be sufficiently large to provide a uniform output distribution. -To reduce the number of iterations, the provided Gray code -should ideally possess the both balanced and locally balanced properties. +To reduce the number of iterations, it can be claimed +that the provided Gray code +should ideally possess both balanced and locally balanced properties. However, none of the two algorithms is compatible with the second one: balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely, locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016} @@ -50,7 +51,7 @@ have mainly allowed them to prove two properties. The former states that if $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced. The latter states that for every $\mathsf{N}$ there -exists a Gray code such that all transition count numbers are +exists a Gray code such that all transition count numbers are 2-powers whose exponents are either equal or differ from each other by 1. However, the authors do not prove that the approach allows to build @@ -83,7 +84,7 @@ two elements have been exchanged. \end{enumerate} It has been proven in~\cite{ZanSup04} that -$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code +$S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code if $S_{\mathsf{N}-2}$ is. However, the step~(\ref{item:nondet}) is not a constructive step that precises how to select the subsequences which ensures that @@ -112,15 +113,15 @@ $|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le 2$. \begin{xpl} -Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to +Let $L^*=000,100,101,001,011,111,$ $110,010$ be the Gray code that corresponds to the Hamiltonian cycle that has been removed in $f^*$. Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and $\textit{TC}_3(3)=4$. Such a Gray code is balanced. Let now -$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$ +$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,$ $0100, 1100, 1101, 1001, 1011, 1010, 1000$ -be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code +be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code is thus totally balanced. On the contrary, for the standard $4$-bits Gray code @@ -133,7 +134,7 @@ the code is neither balanced nor totally balanced. \begin{thrm}\label{prop:balanced} Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by -$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. +$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. There exists then a sequence $l$ in step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ @@ -170,23 +171,21 @@ Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$). These two variables are defined by the system -$$ +\[ \left\{ \begin{array}{lcl} c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\ c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} \end{array} \right. -\qquad \Leftrightarrow -\qquad \left\{ \begin{array}{lcl} d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\ c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}} \end{array} \right. -$$ +\] Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer. Let us first proove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive @@ -282,7 +281,7 @@ a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\ We thus have -$$ +\[ \begin{array}{rcl} \textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) &\ge& @@ -294,9 +293,9 @@ a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\ \frac{2^{\mathsf{N}}-2N}{\mathsf{N}} -2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\ &\ge& -\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\ +\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\ \end{array} -$$ +\] A simple variation study of the function $t:\R \rightarrow \R$ such that $x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that @@ -328,3 +327,9 @@ Notice that all such choices lead to a hamiltonian path. +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% ispell-dictionary: "american" +%%% mode: flyspell +%%% End: