Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/RevolvingDoorCombination

Iterator

  

RevolvingDoorCombination

  

generate combinations in the lexicographic revolving-door Gray code

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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, c1,,ct, of the integers 0..n1, with 0c1ct<n. The combinations c1,,ct are generated in lexicographic order of the alternating sequence ct,ct1,ct2,ct3,,−1t1c1 in the revolving-door Gray code.

Methods

The 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

withIterator&colon;

Construct an iterator that generates all 3-combinations of the integers 0..4.

n,t5,3&colon;

MRevolvingDoorCombinationn&comma;t&colon;

forVinMdoprintf%d\n&comma;Venddo&colon;

0 1 2
0 2 3
1 2 3
0 1 3
0 3 4
1 3 4
2 3 4
0 2 4
1 2 4
0 1 4

Compute the number of iterations.

NumberM

10

(1)

Print the values that changed.

MRevolvingDoorCombinationn&comma;t&comma;append_change&colon;

forVinMdoprintf%d : %d\n&comma;V1..t&comma;V2..1enddo&colon;

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&comma;2&comma;3&comma;4

7

(2)

UnrankM&comma;6

134

(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 Σ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 n1, 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.

MinValCompiler:-CompileMinVal&colon;

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

n,t12,7&colon;

LRandomTools:-Generatelistfloatrange=0..1&comma;method=uniform&comma;n

L0.2342493224&comma;0.1799302829&comma;0.5137385362&comma;0.2907448089&comma;0.8953600369&comma;0.2617341097&comma;0.7780122500&comma;0.06587642124&comma;0.7235311453&comma;0.3157837057&comma;0.05872123377&comma;0.5108327385

(4)

Allocate Arrays used by Val.

SArray1..1&comma;datatype=float8&colon;VArrayL&comma;datatype=float8&colon;

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.

PRevolvingDoorCombinationn&comma;t&comma;append_change&colon;

h,gModuleIteratorP

h,ghasNext,getNext

(5)

Get the first iteration.

pg

p012345612611

(6)

Assign the first iteration as the current minimum.

pminp1..t&colon;

Initialize the running sum and compute the initial minimum.

S1addVi&comma;i=1..n2+addVpi+1&comma;i=1..t

S10.739512051245000

(7)

MabsS1

M0.739512051245000

(8)

Throw away the first iteration.

h&colon;

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

whilehdoMMinValS&comma;V&comma;p&comma;pmin&comma;M&comma;tenddo&colon;

pmin,M

03567810,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.

i1convertpmin+1&comma;list

i11&comma;4&comma;6&comma;7&comma;8&comma;9&comma;11

(10)

i2removemember&comma;seq1..n&comma;i1

i22&comma;3&comma;5&comma;10&comma;12

(11)

L1seqLi&comma;i=i1

L10.2342493224&comma;0.2907448089&comma;0.2617341097&comma;0.7780122500&comma;0.06587642124&comma;0.7235311453&comma;0.05872123377

(12)

L2seqLi&comma;i=i2

L20.1799302829&comma;0.5137385362&comma;0.8953600369&comma;0.3157837057&comma;0.5108327385

(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:

VArrayL&comma;datatype=float8&colon;

CIterator:-RevolvingDoorCombinationn&comma;t&comma;append_change&colon;

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

(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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

Iterator

Iterator[Combination]