Revolving Door Combination - Maple Help

Iterator

 RevolvingDoorCombination
 generate combinations in the lexicographic revolving-door Gray code

 Calling Sequence RevolvingDoorCombination(n, t, opts)

Parameters

 n - posint t - integer[2..n-1] opts - (optional) equation(s) of the form option = value; specify options for the RevolvingDoorCombination command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • append_change = truefalse
 True means append the values that changed in the Array. The returned Array is 3 elements longer.
 – The last element is the value that was removed.
 – The second to last element is the new value.
 – For the first iteration, the last two elements correspond to the changes from the final iteration.
 – The default is false.
 • 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 RevolvingDoorCombination command returns an iterator that generates all t-combinations, ${c}_{1},\dots ,{c}_{t}$, of the integers $0..n-1$, with $0\le {c}_{1}\le \cdots \le {c}_{t}. The combinations ${c}_{1},\dots ,{c}_{t}$ are generated in lexicographic order of the alternating sequence ${c}_{t},-{c}_{t-1},{c}_{t-2},-{c}_{t-3},\dots ,{\left(-1\right)}^{t-1}{c}_{1}$ in the revolving-door Gray code.

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 3-combinations of the integers $0..4$.

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

Compute the number of iterations.

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

Print the values that changed.

 > $M≔\mathrm{RevolvingDoorCombination}\left(n,t,\mathrm{append_change}\right):$
 > $\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}}M\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("%d : %d\n",V\left[1..t\right],V\left[-2..-1\right]\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 0 1 2 : 2 4 0 2 3 : 3 1 1 2 3 : 1 0 0 1 3 : 0 2 0 3 4 : 4 1 1 3 4 : 1 0 2 3 4 : 2 1 0 2 4 : 0 3 1 2 4 : 1 0 0 1 4 : 0 2
 > $\mathrm{Rank}\left(M,⟨2,3,4⟩\right)$
 ${7}$ (2)
 > $\mathrm{Unrank}\left(M,6\right)$
 $\left[\begin{array}{ccc}{1}& {3}& {4}\end{array}\right]$ (3)

Split a list into nearly equal sublists

Consider the task of splitting a list of floats into two sublists of fixed sizes such that the difference between their sums is minimal.

Let ${\mathrm{\Sigma }}_{1}$ and ${\mathrm{\Sigma }}_{2}$ be the sums of each list; we want to minimize $\left|{\mathrm{\Sigma }}_{1}-{\mathrm{\Sigma }}_{2}\right|$. Let $\mathrm{\Sigma }={\mathrm{\Sigma }}_{1}+{\mathrm{\Sigma }}_{2}$.  Then $\left|{\mathrm{\Sigma }}_{1}-{\mathrm{\Sigma }}_{2}\right|=\left|2{\mathrm{\Sigma }}_{1}-\mathrm{\Sigma }\right|$, so we can minimize $\left|{\mathrm{\Sigma }}_{1}-\frac{\mathrm{\Sigma }}{2}\right|$. Given the value of ${\mathrm{\Sigma }}_{1}-\frac{\mathrm{\Sigma }}{2}$ for any iteration, we can compute the value at the next iteration by adding to it the difference of the two elements that change; one is removed from the list, the other is added to the list.

Assign a compilable procedure that returns the current minimum value and updates the Array that stores the corresponding indices, pmin.  Compiled procedures always use 1 as the starting index of an Array, so the elements of p, which vary from $0$ to $n-1$, must be incremented to use as indices into V.

 > MinVal := proc(S :: Array(datatype=float[8])        # one-element Array used for running sum                , V :: Array(datatype=float[8])      # Array corresponding to list of floats                , p :: Array(datatype=integer[4])    # current iterator Array                , pmin :: Array(datatype=integer[4]) # current minimum indices                , M :: float[8]                      # current minimum value                , t :: posint                        # size of sublist               ) option threadsafe;  # used in next section local i, v;     S[1] := S[1] + V[p[t+2]+1] - V[p[t+3]+1];     v := abs(S[1]);     if v < M then         for i to t do             pmin[i] := p[i];         end do;     else         v := M;     end if;     v; end proc:

Compile the procedure.

 > $\mathrm{MinVal}≔\mathrm{Compiler}:-\mathrm{Compile}\left(\mathrm{MinVal}\right):$

Given a list of 12 floats, split it into two lists of 7 and 5 elements, minimizing the difference of their sums.

 > $n,t≔12,7:$
 > $L≔\mathrm{RandomTools}:-\mathrm{Generate}\left(\mathrm{list}\left(\mathrm{float}\left(\mathrm{range}=0..1,\mathrm{method}=\mathrm{uniform}\right),n\right)\right)$
 ${L}{≔}\left[{0.2342493224}{,}{0.1799302829}{,}{0.5137385362}{,}{0.2907448089}{,}{0.8953600369}{,}{0.2617341097}{,}{0.7780122500}{,}{0.06587642124}{,}{0.7235311453}{,}{0.3157837057}{,}{0.05872123377}{,}{0.5108327385}\right]$ (4)

Allocate Arrays used by Val.

 > $S≔\mathrm{Array}\left(1..1,\mathrm{datatype}=\mathrm{float}\left[8\right]\right):$$V≔\mathrm{Array}\left(L,\mathrm{datatype}=\mathrm{float}\left[8\right]\right):$

Construct the iterator, then extract the two procedures, hasNext and getNext, that update and return the next value. Because getNext returns the same Array each time (with different content), we need only call it once.

 > $P≔\mathrm{RevolvingDoorCombination}\left(n,t,'\mathrm{append_change}'\right):$
 > $h,g≔\mathrm{ModuleIterator}\left(P\right)$
 ${h}{,}{g}{≔}{\mathrm{hasNext}}{,}{\mathrm{getNext}}$ (5)

Get the first iteration.

 > $p≔g\left(\right)$
 ${p}{≔}\left[\begin{array}{cccccccccc}{0}& {1}& {2}& {3}& {4}& {5}& {6}& {12}& {6}& {11}\end{array}\right]$ (6)

Assign the first iteration as the current minimum.

 > $\mathrm{pmin}≔p\left[1..t\right]:$

Initialize the running sum and compute the initial minimum.

 > $S\left[1\right]≔-\frac{\mathrm{add}\left(V\left[i\right],i=1..n\right)}{2}+\mathrm{add}\left(V\left[p\left[i\right]+1\right],i=1..t\right)$
 ${{S}}_{{1}}{≔}{0.739512051245000}$ (7)
 > $M≔\mathrm{abs}\left(S\left[1\right]\right)$
 ${M}{≔}{0.739512051245000}$ (8)

Throw away the first iteration.

 > $h\left(\right):$

Loop through remaining iterations, updating the minimum value and Array.

 > $\mathbf{while}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}h\left(\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}}M≔\mathrm{MinVal}\left(S,V,p,\mathrm{pmin},M,t\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 > $\mathrm{pmin},M$
 $\left[\begin{array}{ccccccc}{0}& {3}& {5}& {6}& {7}& {8}& {10}\end{array}\right]{,}{0.00138800444500042364}$ (9)

Use the contents of pmin to form the two sublists of interest. Assign i1 and i2 lists of indices into L corresponding to the two sublists.

 > $\mathrm{i1}≔\mathrm{convert}\left(\mathrm{pmin}+1,\mathrm{list}\right)$
 ${\mathrm{i1}}{≔}\left[{1}{,}{4}{,}{6}{,}{7}{,}{8}{,}{9}{,}{11}\right]$ (10)
 > $\mathrm{i2}≔\mathrm{remove}\left(\mathrm{member},\left[\mathrm{seq}\left(1..n\right)\right],\mathrm{i1}\right)$
 ${\mathrm{i2}}{≔}\left[{2}{,}{3}{,}{5}{,}{10}{,}{12}\right]$ (11)
 > $\mathrm{L1}≔\left[\mathrm{seq}\left(L\left[i\right],i=\mathrm{i1}\right)\right]$
 ${\mathrm{L1}}{≔}\left[{0.2342493224}{,}{0.2907448089}{,}{0.2617341097}{,}{0.7780122500}{,}{0.06587642124}{,}{0.7235311453}{,}{0.05872123377}\right]$ (12)
 > $\mathrm{L2}≔\left[\mathrm{seq}\left(L\left[i\right],i=\mathrm{i2}\right)\right]$
 ${\mathrm{L2}}{≔}\left[{0.1799302829}{,}{0.5137385362}{,}{0.8953600369}{,}{0.3157837057}{,}{0.5108327385}\right]$ (13)

Here we use the Threads package to parallelize the previous task. First we assign a procedure, MinPart, that computes the minimum value for a number of iterations, starting with the iteration of specified rank.

 > MinPart := proc(C :: RevolvingDoorCombination                 , rnk :: posint # rank of first iteration                 , num :: posint    # number of iterations to perform                 , V :: Array       # Array corresponding to list of floats                 , n :: posint      # number of elements in list                 , t :: posint      # size of sublist (L1)                ) local M, S, c, g, h, i, p, pmin;     c := Object(C, 'rank' = rnk);     (h,g) := ModuleIterator(c);     p := g();     h();     pmin := p[1..t];     S := Array(1..1,'datatype'=float[8]);     S[1] := -add(V[i], i=1..n)/2 + add(V[p[i]+1],i=1..t);     M := abs(S[1]);     for i to num while h() do         M := MinVal(S,V,p,pmin,M,t);     end do;     setattribute(M,pmin); end proc:
 > $V≔\mathrm{Array}\left(L,'\mathrm{datatype}'=\mathrm{float}\left[8\right]\right):$
 > $C≔\mathrm{Iterator}:-\mathrm{RevolvingDoorCombination}\left(n,t,'\mathrm{append_change}'\right):$

Use SplitRanks and the Start procedure from Task subpackage to distribute the total number of iterations over all the cores.

 > Threads:-Task:-Start(proc()                      local m;                          m := min(args);                          (setattribute(m), attributes(m)+1);                      end proc                      , 'Tasks'= [MinPart                                  , seq([C, rn[], V, n, t]                                        , rn = SplitRanks(Number(C)))                                 ]                     );
 ${0.00138800444500042364}{,}\left[\begin{array}{ccccccc}{1}& {4}& {6}& {7}& {8}& {9}& {11}\end{array}\right]$ (14)

The result matches that previously computed.

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.3, algorithm R, Revolving-door combinations,  p. 9.

Compatibility

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