X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/d68de43fbfbc44e3363780b39401bf1d2683f9d8..3434a6bb461a09975ace82f172dbf7ea647d882b:/hamilton.tex?ds=sidebyside diff --git a/hamilton.tex b/hamilton.tex index 694bbcf..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,13 +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 -$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the -$\mathsf{N}$ cube. +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. Obviously, the number of iterations $b$ has to be sufficiently large to provide a uniform output distribution. -To reduced 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} @@ -35,21 +37,21 @@ 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 +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 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. +where the authors have explicitly 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 +algorithm. There rigorous 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 +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 @@ -67,30 +69,30 @@ which produces a $n$-bits Gray code. $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 +s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , 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}$ +\item\label{item:u'}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 +\item\label{item:VW} 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 +$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 yielded Gray code is balanced. -Next section shows how to choose the sequence $l$ to have the balancy property. +Next section shows how to choose the sequence $l$ to have the balance property. \subsection{Balanced Codes} -Let us first recall how to formalize the balancy property of a Gray code. +Let us first recall how to formalize the balance 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 @@ -111,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 @@ -131,26 +133,203 @@ 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$. -Then, there exists a sequence $l$ in +Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by +$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)$ are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ for any $i$, $1 \le i \le \mathsf{N}$. +\end{thrm} -\end{thrm} + +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.} +$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 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. +\Leftrightarrow +\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 +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.} +$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 +$d_{\mathsf{N}}$ is $r_{\mathsf{N}}/2$ and is thus a positive integer s.t. +$0 \le d_{\mathsf{N}} <\mathsf{N}$. +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}$ +(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$) +in step (\ref{item:nondet}) of the algorithm. + +Due to the definition of $u'$ in step~(\ref{item:u'}), +$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the + number of element $i$ in the sequence $U$. +It is clear that the number of element $i$ in the sequence $V$ is +$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}). +We thus have the following system: +$$ +\left\{ +\begin{array}{lcl} +3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\ +zi_{\mathsf{N}} + ti_{\mathsf{N}} + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i) +\end{array} +\right. +\qquad +\Leftrightarrow +$$ + +\begin{equation} +\left\{ +\begin{array}{lcl} +zi_{\mathsf{N}} &= & +\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\ +ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}} +\end{array} +\right. +\label{eq:sys:zt1} +\end{equation} + +In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0. +In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$ +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. +We thus have the following system. + + + +\begin{equation} +\left\{ +\begin{array}{lcl} +zi_{\mathsf{N}} &= & +\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\ +ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}} +\end{array} +\right. +\label{eq:sys:zt2} +\end{equation} + +The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$. +When $3 \le N \le 7$, values are defined as follows: +\begin{eqnarray*} +\textit{TC}_{3} & = & [2,2,4] \\ +\textit{TC}_{5} & = & [6,6,8,6,6] \\ +\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\ +\\ +\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. + +When $N \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows: +\begin{equation} +\textit{TC}_{\mathsf{N}}(i) = \left\{ +\begin{array}{l} +a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\ +a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} +\end{array} +\right. +\label{eq:TCN:def} +\end{equation} + + +We thus have +\[ +\begin{array}{rcl} +\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) +&\ge& +a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\ +&\ge& +\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}} +-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\ +&\ge& +\frac{2^{\mathsf{N}}-2N}{\mathsf{N}} +-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\ +&\ge& +\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$. +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. +% \begin{table}[ht] +% $$ +% \begin{array}{|l|l|l|l|l|l|} +% \hline +% \mathsf{N} & 3 & 4 & 5 & 6 & 7\\ +% \hline +% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\ +% \hline +% \end{array} +% $$ +% \label{tab:an} +% \caption{First values of $a_{\mathsf{N}}$} +% \end{table} +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. -\begin{proof} -\end{proof} -\subsection{Toward a local uniform distribution of switches} +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% ispell-dictionary: "american" +%%% mode: flyspell +%%% End: