Other combinatorial functions

The combinat package is an older package, but it still has many useful features. We will highlight those that are likely of interest to engineers.

Notice: The combstruct package is much better designed for permutations, combinations, partitions and compositions than the functions in this package, as there is a uniform interface and the implementation is more efficient.

combinat['graycode'](...)

A gray code is a permutation of the integers from $0$ to $2^n - 1$ such that successive integers differ by only one bit.

[> combinat['graycode']( 5 );

$[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24,$
$25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16]$

[> for gry in combinat['graycode']( 5 ) do
   grybin := convert( gry, binary );

   if gry = 0 then
      padding := 4;
   else
      padding := 5 - length( grybin );
   end if;

   printf( "%*.*s%d\n", padding, padding, "00000", grybin );
end do:
end do:

00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

combinat['multinomal'](...)

If $n = m_1 + m_2 + \cdots + m_k$ then this function returns $\frac{n!}{m_1! m_2! \cdots m_k!}$:

The number of ways of unique ways of permuting a, a, b, b, b, b, b, b, b and c:

[> combinat['multinomial']( 10, 2, 7, 1 );

The number of ways of unique ways of permuting a, a, b, b, b, b, b, c, d, d, d, d, e, e, e, e, e and e:

$360$

[> combinat['multinomial']( 18, 2, 5, 1, 4, 6 );

$1543782240$

combinat['cartprod'](...)

Like the combstruct iterators (see previous topic), the combinat['cartprod'] takes a list of either sets or lists and iterates through all values in the Cartesian product of these lists or sets, so if we have $n$ lists or sets $S_1, \ldots, S_n$, then it will iterate through all lists $[s_1, \ldots, s_n]$ where $s_k \in S_k$:

[> counter := 0:
[> IterCP := combinat['cartprod']( [{a, b, c}, {d, e, f, g}, {h, i, j, k}, {m, n}] ):
[> while not IterCP['finished'] do
     nxstr := IterCP['nextvalue']();
     counter := counter + 1;
     # You can use or manipulate nxstr
     print( nxstr );
end do:

$[a, d, h, m]$
$[a, d, h, n]$
$[a, d, i, m]$
$[a, d, i, n]$
$[a, d, j, m]$
.
.
.
$[c, g, j, n]$
$[c, g, k, m]$
$[c, g, k, n]$

[> counter;

$96$

[> 3*4*4*2;

$96$

Like combstruct, you will note that IterCP is assigned a table, where IterCP['finished'] is false so long as there is another permutation to be iterated through, and IterCP['nextvalue'] is assigned a function which, when called with no arguments, returns the next permutation.