X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/58738f61949e1cc6312f88494db31a201184a407..d1db644de9d68c61725a279fc2ae459c067fbedc:/hamilton.tex diff --git a/hamilton.tex b/hamilton.tex index 8f022c6..0f63e06 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -1,7 +1,7 @@ Many approaches have been developed to solve the problem of building -a Gray code in a $\mathsf{N}$ cube~\cite{}, 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{ZanSup04,DBLP:journals/combinatorics/BhatS96} focus on +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. @@ -27,9 +27,168 @@ 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} are not globally balanced. -This section thus show how the non deterministic approach +This section thus shows how the non deterministic approach presented in~\cite{ZanSup04} has been automatized to provide balanced Hamiltonian paths such that, for each subpart, -the number of swiches of each element is as constant as possible. +the number of switches of each element is as uniform as possible. +\subsection{Analysis of the Robinson-Cohn extension algorithm} +As far as we know three works, +namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, +and~\cite{ZanSup04} have adressed the probem 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 +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 explicitely shown how to construct such a subsequence. +Finally the authors of~\cite{ZanSup04} have presented +the \emph{Robinson-Cohn extension} +algorithm. There rigourous presentation of this one +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 +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. +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. + +\begin{enumerate} +\item \label{item:nondet}Let $l$ be an even positive integer. Find +$u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ +such that $S_{\mathsf{N}-2}$ is the concatenation of +$$ +s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v +$$ +where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence). +\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ + by + $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$ + respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that + $u^R$ is $u$ in reversed order. + The obtained sequence is further denoted as $U$. +\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first +two elements have been exchanged. +\item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$. +\end{enumerate} + +It has been proven in~\cite{ZanSup04} that +$S_{\mathsf{N}}$ is 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 +yielded Gray code is balanced. +Next section shows how to choose the sequence $l$ to have the balancy property. + +\subsection{Balanced Codes} +Let us first recall how to formalize the balancy property of a Gray code. +Let $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence +of a $\mathsf{N}$-bits cyclic Gray code. +The transition sequence +$S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$, +indicates which bit position changes between +codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$. +The \emph{transition count} function +$\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$ +gives the number of times $i$ occurs in $S$, +\textit{i.e.}, the number of times +the bit $i$ has been switched in $L$. + +The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$ +is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$). +It is \emph{balanced} if for any two bit indices $i$ and $j$, +$|\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 +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 +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$, +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} + + +\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$. +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)$ +are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ +for any $i$, $1 \le i \le \mathsf{N}$. +\end{thrm} + + + + + +The proof is done by induction on $\mathsf{N}$. Let us imadialty verify +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$. +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$ +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 +$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$, and $W' = 1, 3, 2, 1,2, 4 $. +Finally, $S_4$ is +$ +2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4 +$ +such that $\textit{TC}_4(i) = 4$ and the theorem is established for +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 transistion 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}} -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 defined. +Moreover, both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are obviously positves. + + +\subsection{Toward a local uniform distribution of switches}