Permutation for numbers in C

Question

Hi programming masses,

I'm trying to write a C function to list all permutations of a set of numbers, in groups of five, including repeat numbers:

15-11-49-43-5
2-30-34-6-11

So it's easy enough to write a function to grab all permutations of a number set and throw them out, but mapped to a certain group size, i'm somewhat stuck..

Thanks

OE

Answer 1

void visit(int *Value, int N, int k)
{
  static level = -1;
  level = level+1; Value[k] = level;

  if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

  level = level-1; Value[k] = 0;
}

For more information you can visit http://www.bearcave.com/random_hacks/permute.html

Answer 2

I would split this up into two problems: a) find all the combinations nCk of your array of size n b) find all the permutations of an array of length k. You said you already know how to do the permutations, so let's focus on the combinations:

void combinations(int *arr, int *comb, int n, int k, int kCurr)
{
    if(kCurr >= k)
    {
        permutations(comb, k);
        return;
    }
    int i;
    for(i=0; i<n; ++i)
    {
        comb[kCurr] = arr[i];
        combinations(arr+i, comb, n-i, k, kCurr+1);
    }
}

which would be called like this:

int myArray[49] = {1, 2, ..., 49};
int myCombs[5];
combinations(myArray, myCombs, 49, 5, 0);

This computes all the combinations 49C5 by building up the array myCombs, and when it is full it calls a function permutations. If permutations is implemented properly then you will print out all permutations of all combinations of 49C5.

EDIT: Duh, you can just do combinations(arr, comb, n, k kCurr+1) as the recursive step, and then just print the array in the base case (or do whatever).

Answer 3

If you know how to find all permutations but not all combinations of size 5, then just find all permutations of:

int A[49] = { 0, 0, ..., 0, 1, 1, 1, 1, 1 };

Each permutation of array A corresponds to a combination containing number (i+1), if and only if A[i] == 1, for each i in [0, 49).

Answer 4

Since repetition is allowed, and the output set is smaller than the input set, it's not actually a permutation that you're after at all.

You're just looking for a simple count:

for (a[0] = 1; a[0] <= 49; a[0]++)
  for (a[1] = 1; a[1] <= 49; a[1]++)
    for (a[2] = 1; a[2] <= 49; a[2]++)
      for (a[3] = 1; a[3] <= 49; a[3]++)
        for (a[4] = 1; a[4] <= 49; a[4]++)
          printf("%d-%d-%d-%d-%d\n", a[0], a[1], a[2], a[3], a[4]);

Answer 5

Do you want to get a specific permutation, like eg

• permutation 1 == 1, 1, 1, 1, 1
• permutation 2 == 1, 1, 1, 1, 2
• permutation 49 == 1, 1, 1, 1, 49
• permutation 50 == 1, 1, 1, 2, 1
• permutation 42000000 == 8, 14, 49, 35, 42

Convert the number you want (minus 1) to base 49 and use the "digits" (plus 1) for the result.

42000000 - 1 = 41999999
41999999 = (7 * 49^4) + (13 * 49^3) + (48 * 49^2) + (34 * 49) + 41
result      8            14            49            35         42