generate combinations in the lexicographic revolving-door Gray code
RevolvingDoorCombination(n, t, opts)
(optional) equation(s) of the form option = value; specify options for the RevolvingDoorCombination command
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. Passing a value greater than one causes the iterator to skip the lower ranks; this can be useful when parallelizing iterators. The starting rank reverts to one when the iterator is reset, reused, or copied.
The RevolvingDoorCombination command returns an iterator that generates all t-combinations, c1,…,ct, of the integers 0..n−1, with 0≤c1≤⋯≤ct<n. The combinations c1,…,ct are generated in lexicographic order of the alternating sequence ct,−ct−1,ct−2,−ct−3,…,−1t−1⁢c1 in the revolving-door Gray code.
If n<t, the iterator generates nothing.
If n=t=0, the iterator generates a single empty Array.
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.
Construct an iterator that generates all 3-combinations of the integers 0..4.
n,t ≔ 5,3:
M ≔ RevolvingDoorCombination⁡n,t:
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.
Print the values that changed.
M ≔ RevolvingDoorCombination⁡n,t,append_change:
forVinMdoprintf⁡%d : %d
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
Split a list into nearly equal sublists
Consider the task of splitting a list of floating-point numbers into two sublists of fixed sizes such that the difference between their sums is minimal.
Let Σ1 and Σ2 be the sums of each list; we want to minimize Σ1−Σ2. Let Σ=Σ1+Σ2. Then Σ1−Σ2=2⁢Σ1−Σ, so we can minimize Σ1−Σ2. Given the value of Σ1−Σ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) # one-element Array used for running sum
, V :: Array(datatype=float) # Array corresponding to list of floats
, p :: Array(datatype=integer) # current iterator Array
, pmin :: Array(datatype=integer) # current minimum indices
, M :: float # current minimum value
, t :: posint # size of sublist
option threadsafe; # used in next section
local i, v;
S := S + V[p[t+2]+1] - V[p[t+3]+1];
v := abs(S);
if v < M then
for i to t do
pmin[i] := p[i];
v := M;
Compile the procedure.
MinVal ≔ Compiler:-Compile⁡MinVal:
Given a list of 12 floating-point numbers, split it into two lists of 7 and 5 elements, minimizing the difference of their sums.
n,t ≔ 12,7:
L ≔ RandomTools:-Generate⁡list⁡float⁡range=0..1,method=uniform,n
Allocate Arrays used by Val.
S ≔ Array⁡1..1,datatype=float8:V ≔ Array⁡L,datatype=float8:
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 ≔ RevolvingDoorCombination⁡n,t,'append_change':
h,g ≔ ModuleIterator⁡P
Get the first iteration.
p ≔ g⁡
Assign the first iteration as the current minimum.
pmin ≔ p1..t:
Initialize the running sum and compute the initial minimum.
S1 ≔ −add⁡Vi,i=1..n2+add⁡Vpi+1,i=1..t
M ≔ S1
Throw away the first iteration.
Loop through remaining iterations, updating the minimum value and Array.
whileh⁡doM ≔ MinVal⁡S,V,p,pmin,M,tend do:
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.
i1 ≔ convert⁡pmin+1,list
i2 ≔ remove⁡member,seq⁡1..n,i1
L1 ≔ seq⁡Li,i=i1
L2 ≔ seq⁡Li,i=i2
Split list using parallel tasks
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();
pmin := p[1..t];
S := Array(1..1,'datatype'=float);
S := -add(V[i], i=1..n)/2 + add(V[p[i]+1],i=1..t);
M := abs(S);
for i to num while h() do
M := MinVal(S,V,p,pmin,M,t);
V ≔ Array⁡L,'datatype'=float8:
C ≔ Iterator:-RevolvingDoorCombination⁡n,t,'append_change':
Use SplitRanks and the Start procedure from Task subpackage to distribute the total number of iterations over all the cores.
m := min(args);
, 'Tasks'= [MinPart
, seq([C, rn, V, n, t]
, rn = SplitRanks(Number(C)))
The result matches that previously computed.
Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 126.96.36.199, algorithm R, Revolving-door combinations, p. 9.
The Iterator[RevolvingDoorCombination] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
The Iterator[RevolvingDoorCombination] command was updated in Maple 2022.
The n and t parameters were updated in Maple 2022.
Download Help Document