|
Calling Sequence
|
|
RevolvingDoorCombination(n, t, opts)
|
|
|
Parameters
|
|
|
n
|
-
|
nonnegint
|
|
t
|
-
|
nonnegint
|
|
opts
|
-
|
(optional) equation(s) of the form option = value; specify options for the RevolvingDoorCombination command
|
|
|
|
|
|
Options
|
|
|
|
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.
|
|
|
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.
|
|
|
|
Description
|
|
|
•
|
The RevolvingDoorCombination command returns an iterator that generates all t-combinations, , of the integers , with . The combinations are generated in lexicographic order of the alternating sequence in the revolving-door Gray code.
|
|
•
|
If , the iterator generates nothing.
|
|
•
|
If , 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.
|
|
|
|
|
Examples
|
|
Construct an iterator that generates all 3-combinations of the integers .
|
>
|
|
|
>
|
|
|
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.
|
>
|
|
|
>
|
|
|
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 and be the sums of each list; we want to minimize . Let . Then , so we can minimize . Given the value of 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 to , 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.
|
>
|
|
Given a list of 12 floating-point numbers, split it into two lists of 7 and 5 elements, minimizing the difference of their sums.
|
>
|
|
|
| (4) |
Allocate Arrays used by Val.
|
>
|
|
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.
|
>
|
|
Get the first iteration.
Assign the first iteration as the current minimum.
Initialize the running sum and compute the initial minimum.
|
>
|
|
Throw away the first iteration.
Loop through remaining iterations, updating the minimum value and Array.
|
>
|
|
|
| (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.
|
>
|
|
|
| (10) |
|
>
|
|
|
| (11) |
|
| (12) |
|
| (13) |
|
|
|
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:
|
|
>
|
|
|
>
|
|
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)))
]
);
|
|
| (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.
|
|
•
|
The Iterator[RevolvingDoorCombination] command was updated in Maple 2022.
|
|
•
|
The n and t parameters were updated in Maple 2022.
|
|
|
|
