Bounded Composition - Maple Help

Online Help

All Products    Maple    MapleSim


Iterator

  

BoundedComposition

  

generate bounded compositions that sum to a constant

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

Calling Sequence

BoundedComposition(M, T, opts)

Parameters

M

-

{list,Vector,Array}(nonnegint); bounds of components of each composition

T

-

nonnegint; sum of each composition

opts

-

(optional) equation(s) of the form option = value; specify options for the BoundedComposition command

Options

• 

compile = truefalse

  

True means compile the iterator. The default is true.

Description

• 

The BoundedComposition command returns an iterator that generates bounded compositions in reverse lexicographic order.

• 

A bounded composition is a sequence of integers, r1,,rn, such that T=k=1nrk and 0rkMk, for k1n, with n=numelemsM.

• 

A bounded composition with M=m1,m2,,mn and sum T is equivalent to a multicombination of T elements chosen from a multiset of n distinct elements with mk the multiplicity of the k-th element.

Examples

withIterator:

BBoundedComposition5,2,4,8:

PrintB,showrank:

1: 5 2 1
2: 5 1 2
3: 4 2 2
4: 5 0 3
5: 4 1 3
6: 3 2 3
7: 4 0 4
8: 3 1 4
9: 2 2 4

Contingency Table

• 

A contingency table is an m×n matrix of nonnegative integers aij with given row sums Ri=j=1naij and column sums Cj=i=1maij. Given the m-vector R and n-vector C, we want to compute the number of distinct contingency tables. Use a bounded-composition with M=C and T=R1 to generate a valid first row. Use a bounded-composition with M=Ck=1i1rk and T=Ri, where rk is the content of the k-th row, to generate a valid i-th row. The last row is fixed by preceding rows. The following procedure uses a recursive procedure, cnt, to generate and enumerate the iterators for each row.

Cnt := proc(R :: ~Array, C :: ~Array)
local cnt,m;
    if add(R) <> add(C) then
        error "row and column sums must be equal";
    end if;
    m := numelems(R);
    cnt := proc(i, c)
    local r;
        if i = m then
            return 1;  # final row
        else
            add(cnt(i+1, c-r), r = BoundedComposition(c,R[i]));
        end if;
    end proc;
    cnt(1, C);
end proc:

• 

Try it with a known case (value must be 5!).

Cnt`$``$`1&comma;5&comma;2

120

(1)
• 

Try a simple case

Cnt2&comma;3&comma;4&comma;1&comma;3&comma;5

24

(2)

References

  

Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions,sec. 7.2.1.3, exercise 60, p. 30, and answers, algorithm Q, pp. 98-99.

Compatibility

• 

The Number method was updated in Maple 2020.

• 

The Iterator[BoundedComposition] command was introduced in Maple 2016.

• 

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

See Also

combinat[choose]

Iterator