The combstruct package (combinatorial structures) is one of the hidden gems in Maple, mostly because the help pages make it so difficult to understand what the package is capable of. As a consequence, users often revert to the more clearly documented combinat package.
First, the philosophy: define combinatorial structures, and then define functions that can query or work with such structures.
There are four possible structures, including permutations, combinations, partitions or compositions.
The structures
[> p1 := Permutation( [a, b, c, c] ): [> p2 := Permutation( {x, y, z} ): [> p3 := Permutation( 7 ):
represents all permutations of the entries in the list, the entries in the set, or the integers from 1 to, in this case, 7.
For example, all permutations of the elements in the set {x, y, z} includes the six lists [x, y, z], [x, z, y], [z, x, y], [z, y, x], [y, z, x] and [y, x, z].
The structures
[> c1 := Combination( [a, b, c, c] ): [> c2 := Combination( {x, y, z} ): [> c3 := Combination( 8 ):
represents all combinations of the entries in the list, the entries in the set, or the integers from 1 to, in this case, 8.
For example, all combinations of the elements in the set [a, a, b] includes the six lists [], [a], [b], [a, a], [a, b] and [a, a, b].
If the entries in the list are unique, or given a set or an integer, then the combinations equals the subsets.
Given an integer $n$, the structure Partition( n ) represents all possible sums of positive integers that equals $n$ without regard for order.
For example, Partition( 4 ) includes the possibilities of $1 + 1 + 1 + 1$, $1 + 1 + 2$, $1 + 3$, $2 + 2$ and $4$.
These are represented as lists, so [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3] and [4].
If you wanted all possible partitions, you could subsequently ask for all permutations of each of these partitions, or you can ask for all compositions (see next).
Given an integer $n$, the structure Composition( n ) represents all possible sums of positive integers that equals $n$ but taking order into account.
For example, Composition( 4 ) describes all permutations of all possible partitions of $4$.
These are represented as lists, so
These are represented as lists, so [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2], [1, 3], [3, 1] and [4].
The structures listed above are inert, meaning that they only represent what is described. We can now make queries from these structures.
We will assume you have executed the following:
[> with( combstruct ): [> perm := Permutation( [a, a, 2, 3] ): [> comb := Combination( {a, b, c} ): [> part := Partition( 7 ): [> comp := Composition( 5 ):
The count(...) function returns the number of possible partitions, combinations, partitions, or compositions, without actually generating them and counting them:
[> count( perm );
$12$
[> count( comb );
$8$
[> count( part );
$15$
[> count( comp );
$16$
You can also ask for a count of all different permutations of $k$ objects chosen from the list, all combinations of $k$ objects, all partitions that have $k$ integers, and all combinations that have $k$ integers by providing a size option:
[> count( perm, 'size' = 2 );
$7$
[> count( comb, 'size' = 2 );
$3$
[> count( part, 'size' = 2 );
$3$
[> count( comp, 'size' = 2 );
$46$
This command is useful if you just need to know how many such structures there are.
The draw(...) function randomly selects or draws (as in, out of a hat) one possible permutation, combination, partition or composition from the given structure. You may want to use such a function if you wanted to test your implementation on a random instance of a combinatorial structure, as it may be infeasible to test, for example, all permutations of fifty unique inputs.
[> draw( perm );
$[a, 2, 3, a]$
[> draw( perm );
$[2, 3, a, a]$
[> draw( comb );
$[b]$
[> draw( comb );
$[a, b]$
[> draw( part );
$[1, 1, 1, 1, 3]$
[> draw( part );
$[1, 1, 1, 4]$
[> draw( comp );
$[1, 2, 1, 1]$
[> draw( comp );
$[3, 1, 1]$
Each possible permutation, combination, partition or composition is equally likely. You can also specify the size:
[> draw( perm, 'size' = 3 );
$[2, a, 3]$
[> draw( perm, 'size' = 3 );
$[a, a, 2]$
[> draw( comb, 'size' = 2 );
$[a, c]$
[> draw( comb, 'size' = 2 );
$[a, b]$
[> draw( part, 'size' = 3 );
$[1, 1, 5]$
[> draw( part, 'size' = 3 );
$[2, 2, 3]$
[> draw( comp, 'size' = 3 );
$[1, 1, 3]$
[> draw( comp, 'size' = 3 );
$[2, 1, 2]$
This command is useful if you need one random sample from the structures there are; for example,
[> # Run 10 random permutations on 100 [> to 10 do prm := draw( Permutation( 100 ) ); print( add( k*prm[k], k = 1..100 ) ); end do:
$265462$
$248881$
$252703$
$250004$
$259625$
$249077$
$262160$
$235782$
$249772$
$250356$
The allstructs(...) function returns a list of all possible instances of the particular structure. This is a resource intensive operation (both in time and memory), so please see iterstructs(...) before you use this function.
[> allstructs( perm );
$[[a, a, 2, 3], [a, a, 3, 2], [a, 2, a, 3], [a, 2, 3, a], [a, 3, a, 2],$
$[a, 3, 2, a], [2, a, a, 3], [2, a, 3, a], [2, 3, a, a], [3, a, a, 2],$
$[3, a, 2, a], [3, 2, a, a]]$
[> allstructs( comb );
$[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]$
[> allstructs( part );
$[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 2, 2],$
$[1, 2, 2, 2], [1, 1, 1, 1, 3], [1, 1, 2, 3], [2, 2, 3], [1, 3, 3],$
$[1, 1, 1, 4], [1, 2, 4], [3, 4], [1, 1, 5], [2, 5], [1, 6], [7]]$
[> allstructs( comp );
$[[5], [1, 4], [2, 3], [3, 2], [4, 1], [1, 1, 3], [1, 2, 2],$
$[1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1], [1, 1, 1, 2],$
$[1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]$
This is very expensive in terms of memory, especially when there are many permutations, combinations, etc. You can also specify the size:
[> allstructs( perm, 'size' = 3 );
$[[a, a, 2], [a, a, 3], [a, 2, a], [a, 2, 3], [a, 3, a],$
$[a, 3, 2], [2, a, a], [2, a, 3], [2, 3, a], [3, a, a],$
$[3, a, 2], [3, 2, a]]$
[> allstructs( comb, 'size' = 2 );
$[[a, b], [a, c], [b, c]]$
[> allstructs( part, 'size' = 3 );
$[[1, 1, 5], [1, 2, 4], [1, 3, 3], [2, 2, 3]]$
[> allstructs( comp, 'size' = 3 );
$[[1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1]]$
The iterstructs(...) function returns an iterator that allows you to step through all of the possible instances without actually generating all of them simultaneously, and is therefore very superior to using allstructs(...). The iterator only goes forward through all possible structures, and once it is finished, you cannot reset it; instead, if you want to go through the structures again, you must regenerate the iterator. We will only show one example:
[> IterP := iterstructs( Permutation( [a, a, b, b, b] ) ): [> while not IterP['finished'] do nxstr := IterP['nextvalue'](); # You can use or manipulate nxstr print( nxstr ); end do:
$[a, a, b, b, b]$
$[a, b, a, b, b]$
$[a, b, b, a, b]$
$[a, b, b, b, a]$
$[b, a, a, b, b]$
$[b, a, b, a, b]$
$[b, a, b, b, a]$
$[b, b, a, a, b]$
$[b, b, a, b, a]$
$[b, b, b, a, a]$
You will note that IterP is assigned a table, where IterP['finished'] is false so long as there is another permutation to be iterated through, and IterP['nextvalue'] is assigned a function which, when called with no arguments, returns the next permutation.
There are other features of this package, but they are beyond the scope of applications for engineering undergraduate students.