Binary Gray Code - Maple Help

Iterator

 BinaryGrayCode
 generate n-bit binary Gray code

 Calling Sequence BinaryGrayCode(n, opts)

Parameters

 n - nonnegint; number of bits opts - (optional) equation(s) of the form option = value; specify options for the BinaryGrayCode command

Options

 • append_change = truefalse
 True means append an integer indicating the change to the output Array. The magnitude of the integer is the index that changed, the sign is the direction of the change. The default is false.
 • compile = truefalse
 True means compile the iterator. The default is true.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The BinaryGrayCode command returns an iterator that generates binary Gray code. The output is a one-dimensional Array of zeros and ones. A binary Gray code changes one element at each transition.
 • The n parameter specifies the number of integers in the output.

Methods

In addition to the common iterator methods, this iterator object has the following methods. The self parameter is the iterator object.

 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.
 • Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Construct an iterator that loops through all 3-bit binary Gray codes.

 > $M≔\mathrm{BinaryGrayCode}\left(3\right):$
 > $\mathrm{seq}\left(m\left[\right],m=M\right)$
 $\left[\begin{array}{ccc}{0}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {0}& {1}\end{array}\right]$ (1)

Compute the number of iterations.

 > $\mathrm{Number}\left(M\right)$
 ${8}$ (2)

Use the append_change option to display the index that changed and the direction of the change.

 > $M≔\mathrm{BinaryGrayCode}\left(3,\mathrm{append_change}\right):$
 > $\mathrm{seq}\left(m\left[\right],m=M\right)$
 $\left[\begin{array}{cccc}{0}& {0}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {1}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{cccc}{0}& {1}& {0}& {-1}\end{array}\right]{,}\left[\begin{array}{cccc}{0}& {1}& {1}& {3}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {0}& {1}& {-2}\end{array}\right]{,}\left[\begin{array}{cccc}{0}& {0}& {1}& {-1}\end{array}\right]$ (3)

Return the element with rank equal to 4.

 > $\mathrm{Unrank}\left(M,4\right)$
 $\left[\begin{array}{ccc}{0}& {1}& {0}\end{array}\right]$ (4)

Simplified Dudney's Century Puzzle

Find all sequences such that $\mathrm{1 ∘ 2 ∘ 3 ∘ ⋯ ∘ 9 = 100}$, with $\circ$ either addition or multiplication, and normal binding strengths.

Assign a procedure that converts a boolean Vector to the relevant string.

 > VecToStr := proc(V) local i;     cat("",seq('(i,if(V[i]=0,"+","*"))',i=1..8),"9=100") end proc:

Construct an iterator that steps through all 8-bit boolean Vectors.

 > $\mathrm{iter}≔\mathrm{BinaryGrayCode}\left(8\right)$
 ${\mathrm{iter}}{≔}{\mathrm{BinaryGrayCode}}{}\left({8}\right)$ (5)

Use the iterator to generate all the solutions.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}v\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{iter}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}s≔\mathrm{VecToStr}\left(v\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathbf{if}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{parse}\left(s\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%s\n",s\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 1*2*3*4+5+6+7*8+9=100 1*2*3+4+5+6+7+8*9=100 1+2+3+4+5+6+7+8*9=100

Compute the Permanent of a Matrix with Ryser's algorithm

The permanent of a Matrix is similar to the determinant, but in the definition the signatures of the permutations are ignored. Ryser's algorithm is an efficient method for computing the permanent.

 > Permanent := proc(M::Matrix) local G, J, V, aj, g, h, i, k, m, n, s, sj, sig;     m, n := op(1, M);     if m <> n then         error "expecting a square Matrix, got dimensions %1, %2", m, n     end if;     G := Iterator:-BinaryGrayCode(n,'append_change');     V := Vector(n);     (h,g) := ModuleIterator(G);     h();     J := g();     s := 0;     sig := -1;     while h() do         sj := sign(J[-1]);         aj := abs(J[-1]);         for i to n do             V[i] := V[i] + sj * M[i,aj];         end do;         s := s + sig*mul(V[k], k=1..n);         sig := -sig;     end do;     expand((-1)^n*s); end proc:

Compare the time and memory usage of this routine with the one provided in LinearAlgebra[Permanent].

 > $M≔\mathrm{Matrix}\left(11,\mathrm{rand}\left(11\right)\right):$
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{Permanent}\left(M\right)\right)$
 memory used=1.78MiB, alloc change=0 bytes, cpu time=45.00ms, real time=45.00ms, gc time=0ns
 ${4852455795314422}$ (6)
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{LinearAlgebra}:-\mathrm{Permanent}\left(M\right)\right)$
 memory used=3.10MiB, alloc change=0 bytes, cpu time=59.00ms, real time=59.00ms, gc time=0ns
 ${4852455795314422}$ (7)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.1, generating all n-tuples, algorithm L, loopless Gray binary generation, p. 10.

Compatibility

 • The Iterator[BinaryGrayCode] command was introduced in Maple 2016.