Chase - Maple Help

Iterator

 Chase
 generate all (s,t)-combinations of zeros and ones in near-perfect order

 Calling Sequence Chase(s, t, opts)

Parameters

 s - nonnegint; number of zeros in each combination t - nonnegint; number of ones in each combination opts - (optional) equation(s) of the form option = value; specify options for the Chase command

Options

 • 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 Chase command returns an iterator that generates all combinations of s zeros and t ones in Chase's sequence.
 • Transitions are strongly homogeneous; each transition is either $01↔10$ or $001↔100$.
 • The s parameter is the number of zeros in each combination.
 • The t parameter is the number of ones in each combination.

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 generates all combinations of three 0's and two 1's, in Chase's sequence.

 > $s,t≔3,2:$
 > $M≔\mathrm{Chase}\left(s,t\right):$
 > $\mathrm{Print}\left(M,'\mathrm{showrank}'\right):$
 1: 0 0 0 1 1  2: 0 0 1 0 1  3: 1 0 0 0 1  4: 0 1 0 0 1  5: 0 1 1 0 0  6: 1 0 1 0 0  7: 1 1 0 0 0  8: 1 0 0 1 0  9: 0 1 0 1 0 10: 0 0 1 1 0

Compute the number of iterations.

 > $\mathrm{Number}\left(M\right)$
 ${10}$ (1)

Return the element with rank equal to 4.

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

 > $N≔\mathrm{Object}\left(M,\mathrm{rank}=4\right):$
 > $\mathrm{seq}\left(v\left[\right],v=N\right)$
 $\left[\begin{array}{ccccc}{0}& {1}& {0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccccc}{0}& {1}& {1}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccccc}{1}& {0}& {1}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccccc}{1}& {1}& {0}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccccc}{1}& {0}& {0}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccccc}{0}& {1}& {0}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccccc}{0}& {0}& {1}& {1}& {0}\end{array}\right]$ (3)

Winning Patterns

Enumerate the different ways to win a first-to-win $w$ match. Let zero be a loss and one a win by the side that wins the match. Each winning pattern has $w$ ones, zero to $w-1$ zeros, and ends in a one.

Basic Approach

We can use a double loop to generate each winning pattern. The outer loop sets the number of losses, the inner loop generates patterns with $l$ zeros, $w-1$ ones, and appends a final one.

 > $w≔3:$$P≔\mathrm{Array}\left(1..2w-1\right):$$\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}l\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{from}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}w-1\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}}t≔w+l-1;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}P\left[t+1\right]≔1;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Chase}\left(l,w-1\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}c\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}C\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}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}P\left[1..t\right]≔c\left[\right];\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("%\left\{\right\}d\n",P\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{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1

Iterator Solution

The following code assigns an appliable object, Win, that returns an iterator that generates the winning pattern. It illustrates how the iterators in this package can be used to construct specialized iterators.

 > Win := module() option object; local w := w;  # self-assignment is to avoid a mint nag export     ModuleApply :: static := proc(w :: posint)         Object(Win, w, _rest);     end proc; export     ModuleCopy :: static := proc(self :: Win                                  , proto :: Win                                  , w :: posint := proto:-w                                 )         self:-w := w;     end proc; # Assign the ModuleIterator, which returns the two procedures, # hasNext and getNext, used by Maple to iterate.  Because these # procedures do not have direct access to the object's locals, # we have to copy them to a local of ModuleIterator; here we # copy the 'w' local. export     ModuleIterator :: static := proc(self :: Win)     local C,L,P,first,h,hasNext,g,getNext,l,o,w;         w := self:-w;         # copy needed         l := -1;              # incremented when a new Chase iterator is created         P := Array(1..2*w-1); # stores the output         first := true;        # flag to handle first time         # Assign the local hasNext.  This does all the work.         hasNext := proc()         local val;             if not first and h() then                 val := true;             elif l = w-1 then                 return false;             else                 first := false;                 l := l+1;                 # Set the final win position to 1.                 P[l+w] := 1;                 # Extract the has/get procedures from the Chase iterator.                 # Call the get procedure (g) to extract the output Vector, o,                 # which we will copy into P when it is updated.  Call the has                 # procedure (h), which updates o and returns the boolean value                 # used by this iterator.                 (h,g) := :-ModuleIterator(Iterator:-Chase(l,w-1));                 o := g();                 val := h();             end if;             P[1..l+w-1] := o; # copy output to P             val;              # return true or false         end proc;         getNext := proc() P end proc;         (hasNext, getNext);     end proc; end module:

Print the results from using the iterator.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}w\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{Win}\left(3\right)\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}}\mathrm{printf}\left("%\left\{\right\}d\n",w\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.3, generating all combinations, algorithm C (Chase's sequence), p. 13.

Compatibility

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