X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/236f25b2f3a081b11c71bedad6d044d695ce2cca..23dcb45dd9df2aff12c4ca42d4d96ff2c039358e:/hamilton.tex?ds=inline diff --git a/hamilton.tex b/hamilton.tex index dc19f08..a48fc62 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -1,13 +1,13 @@ 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, the number of transitions of each element must differ at most by 2. -This uniformity is a global property on the cycle, \textit{i.e.} +This uniformity is a global property on the cycle, \textit{i.e.}, a property that is established while traversing the whole cycle. -On the opposite side, when the objective is to follow a subpart +On the other hand, when the objective is to follow a subpart of the Gray code and to switch each element approximately the same amount of times, local properties are wished. @@ -15,16 +15,17 @@ For instance, the locally balanced property is studied in~\cite{Bykov2016} 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 -$b$ times to produce a pseudo random number, -\textit{i.e.} a vertex in the -$\mathsf{N}$ cube. +$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an Hamiltonian +cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated +$b$ times to produce a pseudorandom number, +\textit{i.e.}, a vertex in the +$\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 +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: +However, both algorithms are incompatible 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} are not globally balanced. @@ -39,29 +40,29 @@ namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, and~\cite{ZanSup04} have addressed the problem of providing an approach to produce balanced gray code. The authors of~\cite{Robinson:1981:CS} introduced an inductive approach -aiming at producing balanced Gray codes, provided the user gives +aiming at producing balanced Gray codes, assuming the user gives a special subsequence of the transition sequence at each induction step. -This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96} -where the authors have explicitly shown how to construct such a subsequence. +This work has been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96} +where the authors have explicitly shown how to build such a subsequence. Finally the authors of~\cite{ZanSup04} have presented the \emph{Robinson-Cohn extension} -algorithm. There rigorous presentation of this one -have mainly allowed them to prove two properties. +algorithm. Their rigorous presentation of this algorithm +has 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 -(totally balanced) Gray code. +(totally balanced) Gray codes. What follows shows that this fact is established and first recalls the approach. Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is $S_{\mathsf{N}-2}$. What follows is the \emph{Robinson-Cohn extension} method~\cite{ZanSup04} -which produces a $n$-bits Gray code. +which produces a $\mathsf{N}$-bits Gray code. \begin{enumerate} \item \label{item:nondet}Let $l$ be an even positive integer. Find @@ -83,12 +84,12 @@ 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 +However, step~(\ref{item:nondet}) is not a constructive +step that precises how to select the subsequences which ensure that yielded Gray code is balanced. -Next section shows how to choose the sequence $l$ to have the balance property. +Following sections show how to choose the sequence $l$ to have the balance property. \subsection{Balanced Codes} Let us first recall how to formalize the balance property of a Gray code. @@ -112,20 +113,18 @@ $|\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,$ -$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 +Let $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 is thus totally balanced. On the contrary, for the standard $4$-bits Gray code -$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$ -$1101,1111,1110,1010,1011,1001,1000$, +$L^{\textit{st}}=0000,0001,0011, +0010,0110,0111,0101,0100,$ \newline $1100,1101,1111,1110,1010,1011,1001,1000$, we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and the code is neither balanced nor totally balanced. \end{xpl} @@ -133,7 +132,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)$ @@ -146,13 +145,13 @@ for any $i$, $1 \le i \le \mathsf{N}$. The proof is done by induction on $\mathsf{N}$. Let us immediately verify -that it is established for both odd and even smallest values, \textit{i.e.} +that it is established for both odd and even smallest values, \textit{i.e.}, $3$ and $4$. -For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$. +For the initial case where $\mathsf{N}=3$, \textit{i.e.}, $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$. Thus again the algorithm successively produces $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$. Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem. - For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ + For the initial case where $\mathsf{N}=4$, \textit{i.e.}, $\mathsf{N-2}=2$ we successively have: $S_1=1,2,1,2$, $l=4$, $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$. Thus again the algorithm successively produces @@ -168,32 +167,30 @@ odd and even initial values. For the inductive case, let us first define some variables. 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 +Both of these 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 +Let us first prove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive integers. Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be -the quotient and the remainder in the Euclidean disvision -of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.} +the quotient and the remainder in the Euclidean division +of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.}, $2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$. First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. Next, $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently @@ -203,7 +200,7 @@ The proof for $c_{\mathsf{N}}$ is obvious. For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) -be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ +be the occurrence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ (resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$) in step (\ref{item:nondet}) of the algorithm. @@ -241,7 +238,7 @@ or to $a_{\mathsf{N}}+2$), the variable $zi_{\mathsf{N}}$ is thus an integer. Let us now prove that the resulting system has always positive integer solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. -This latter consraint is obviously established if the system has a solution. +This latter constraint is obviously established if the system has a solution. We thus have the following system. @@ -267,7 +264,7 @@ When $3 \le N \le 7$, values are defined as follows: \textit{TC}_{4} & = & [4,4,4,4] \\ \textit{TC}_{6} & = & [10,10,10,10,12,12] \\ \end{eqnarray*} -It is not hard to verify that all these instanciations verify the aformentioned contraints. +It is not difficult to check that all these instanciations verify the aforementioned constraints. When $N \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows: \begin{equation} @@ -282,7 +279,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,13 +291,13 @@ 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 -its derivative is strictly postive if $x \ge 6$ and $t(8)=224$. +its derivative is strictly positive if $x \ge 6$ and $t(8)=224$. The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive for any $\mathsf{N} \ge 8$ and the proof is established. @@ -322,7 +319,7 @@ for any $\mathsf{N} \ge 8$ and the proof is established. For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions among $\textit{TC}_{\mathsf{N}}(i)$, which leads to ${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities. -Notice that all such choices lead to a hamiltonian path. +Notice that all such choices lead to an Hamiltonian path.