Tuesday, April 1, 2008

Permutations with Duplicates in C

Calculating permutations has some fairly nifty algorithms out there. I recently ran into a permutation problem for which I couldn't find an existing algorithm. I admit that I didn't look too hard though. Basically, I needed the permutations of the elements of a set of size N over K slots. However, the permutations should include duplicate elements from the set, as K > N is valid configuration. This corresponds to NK permutations. Most algorithms I found did not permit duplicate elements.

As an example of an application for such a permutation algorithm, imagine the set of all function signatures of arity K-1 over N types. This corresponds to K slots with N possible choices for each slot.

I devised a fairly simple implementation of such a permutation algorithm. Essentially, N forms the base of an arbitrary-precision integer of size K. In other words, we have an array of elements with a maximum of N which index our set. To permute, we simply increment the first element and propagate any overflow across the rest of the array. If the carry is 1 when we're done iterating over the whole array, then we're done generating permutations.

Calculating permutations has been reduced to counting! Here is the C code:
`#include <stdio.h>void print(const unsigned *slots, const unsigned K){  unsigned i;  for (i = 0; i < K; ++i) {    printf("%4d", slots[i] );  }  printf("\n");}unsigned incr(unsigned *slots, const unsigned K, const unsigned N) {  unsigned i, carry;  print(slots, K);  for (i=0, carry=1; i < K; ++i) {    unsigned b = slots[i] + carry;    carry = b/N;    slots[i] = b % N;  }  return !carry;}void count(const unsigned N, const unsigned K) {  unsigned i;  unsigned *slots = calloc(K, sizeof(unsigned));  while(incr(slots, K, N)) {  }}//output://   0   0   0//   1   0   0//   0   1   0//   1   1   0//   0   0   1//   1   0   1//   0   1   1//   1   1   1int main(int argc, char ** argv) {  count(2, 3);  getchar();}`

The only assumption is that N is less than UINT_MAX. Also, for some insane reason that I cannot fathom, I can't get the slots to print in reverse order. The trivial reversal of the print loop induces an access violation under Windows:
`void print(const unsigned *slots, const unsigned K){  unsigned i;  for (i = K-1; i >= 0; --i) {    printf("%4d", slots[i] );  }  printf("\n");}`

The mind boggles.

[Edit: a commenter pointed out the problem, so the solution can be found in the comments.]

Brandon said...

Your reverse print function coredumps because i is unsigned, so your termination test in the for loop (i >= 0) never fails.

Sandro Magi said...

Damnit, you're right. I thought the 0 condition properly handled it, but of course it doesn't since 0 is a valid value, and overflow is ignored in C. I'm too used to working in languages with overflow checking I suppose. :-)

The correct loop is of course:

void print(const unsigned *slots, const unsigned K)
{
unsigned i;
for (i = K-1; i >= 0-1; --i) {
printf("%4d", slots[i] );
}
printf("\n");
}

Brandon said...

Using the test (i >= 0-1) should not print anything because K >= 0-1 forall K if your using unsigned arithmetic. I would change to signed arithmetic, but if you want to stick with unsigned you can use i < 0-1. Not very intuitive if your reading it though....

Sandro Magi said...

> Using the test (i >= 0-1)
> should not print anything
> because K >= 0-1 forall K if