Iterator
RevolvingDoorCombination
generate combinations in the lexicographic revolving-door Gray code
Calling Sequence
Parameters
Options
Description
Examples
References
Compatibility
RevolvingDoorCombination(n, t, opts)
n
-
nonnegint
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−1c1 in the revolving-door Gray code.
If n<t, the iterator generates nothing.
If n=t=0, the iterator generates a single empty Array.
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.
withIterator:
Construct an iterator that generates all 3-combinations of the integers 0..4.
n,t≔5,3:
M≔RevolvingDoorCombinationn,t:
PrintM,showrank:
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.
NumberM
10
Print the values that changed.
M≔RevolvingDoorCombinationn,t,append_change:
forVinMdoprintf%d : %d\n,V1..t,V−2..−1enddo:
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
RankM,2,3,4
7
UnrankM,6
134
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[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.
MinVal≔Compiler:-CompileMinVal:
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:-Generatelistfloatrange=0..1,method=uniform,n
L≔0.2342493224,0.1799302829,0.5137385362,0.2907448089,0.8953600369,0.2617341097,0.7780122500,0.06587642124,0.7235311453,0.3157837057,0.05872123377,0.5108327385
Allocate Arrays used by Val.
S≔Array1..1,datatype=float8:V≔ArrayL,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≔RevolvingDoorCombinationn,t,append_change:
h,g≔ModuleIteratorP
h,g≔hasNext,getNext
Get the first iteration.
p≔g
p≔012345612611
Assign the first iteration as the current minimum.
pmin≔p1..t:
Initialize the running sum and compute the initial minimum.
S1≔−addVi,i=1..n2+addVpi+1,i=1..t
S1≔0.739512051245000
M≔absS1
M≔0.739512051245000
Throw away the first iteration.
h:
Loop through remaining iterations, updating the minimum value and Array.
whilehdoM≔MinValS,V,p,pmin,M,tenddo:
pmin,M
03567810,0.00138800444500042364
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≔convertpmin+1,list
i1≔1,4,6,7,8,9,11
i2≔removemember,seq1..n,i1
i2≔2,3,5,10,12
L1≔seqLi,i=i1
L1≔0.2342493224,0.2907448089,0.2617341097,0.7780122500,0.06587642124,0.7235311453,0.05872123377
L2≔seqLi,i=i2
L2≔0.1799302829,0.5137385362,0.8953600369,0.3157837057,0.5108327385
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(); 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≔ArrayL,datatype=float8:
C≔Iterator:-RevolvingDoorCombinationn,t,append_change:
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.00138800444499997955,14678911
The result matches that previously computed.
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.
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.
See Also
Iterator[Combination]
Download Help Document
