Iterator - Maple Programming Help

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

Iterator

 BoundedComposition
 generate bounded compositions that sum to a constant

 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, $\left({r}_{1},\dots ,{r}_{m}\right)$, such that $T=\sum _{k=1}^{m}{r}_{k}$ and $0\le {r}_{k}\le {M}_{k}$, for $k\in \left\{1\dots m\right\}$, with $m=\mathrm{numelems}\left(M\right)$.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}V\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{BoundedComposition}\left(\left[5,2,4\right],8\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%d\n",V\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 5 2 1 5 1 2 4 2 2 5 0 3 4 1 3 3 2 3 4 0 4 3 1 4 2 2 4

Contingency Table

 • A contingency table is an $m×n$ matrix of nonnegative integers $\left({a}_{\mathrm{ij}}\right)$ with given row sums ${R}_{i}=\sum _{j=1}^{n}{a}_{\mathrm{ij}}$ and column sums ${C}_{j}=\sum _{i=1}^{m}{a}_{\mathrm{ij}}$. 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={R}_{1}$ to generate a valid first row. Use a bounded-composition with $M=C-\sum _{k=1}^{i-1}{r}_{k}$ and $T={R}_{i}$, where ${r}_{k}$ 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!).
 > $\mathrm{Cnt}\left(\mathrm{}\left(\left[\mathrm{}\left(1,5\right)\right],2\right)\right)$
 ${120}$ (1)
 • Try a simple case
 > $\mathrm{Cnt}\left(\left[2,3,4\right],\left[1,3,5\right]\right)$
 ${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.