hamilton.tex

   1 Many approaches have been developed to solve the problem of building
   2 a Gray code in a $\mathsf{N}$ cube~\cite{}, according to properties
   3 the produced code has to verify.
   4 For instance,~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} focus on
   5 balanced Gray codes. In the transition sequence of these codes,
   6 the number of transitions of each element must differ
   7 at most by 2.
   8 This uniformity is a global property on the cycle, \textit{i.e.}
   9 a property that is established while traversing the whole cycle.
  10 On the opposite side, when the objective is to follow a subpart
  11 of the Gray code and to switch each element approximately the
  12 same amount of times,
  13 local properties are wished.
  14 For instance, the locally balanced property is studied in~\cite{Bykov2016}
  15 and an algorithm that establishes locally balanced Gray codes is given.
  16
  17 The current context is to provide a function
  18 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian
  19 cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
  20 $b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the
  21 $\mathsf{N}$ cube.
  22 Obviously, the number of iterations $b$ has to be sufficiently large
  23 to provide a uniform output distribution.
  24 To reduced the number of iterations, the provided Gray code
  25 should ideally possess the both balanced and locally balanced properties.
  26 However, none of the two algorithms is compatible with the second one:
  27 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
  28 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
  29 are not globally balanced.
  30 This section thus show how the non deterministic approach
  31 presented in~\cite{ZanSup04} has been automatized to provide balanced
  32 Hamiltonian paths such that, for each subpart,
  33 the number of swiches of each element is as constant as possible.
  34
  35