CODEWITHSUNDEEP
carraysalgorithmrecursionpermutation
F22lightning
F22lightning

Reputation: 640

How to print out all the permutation of a range of numbers in C using recursion?

I am trying to make a recursive function that would print out all the permutations with duplicates of an array of integers, but the numbers have a range, and the array size ranges as well. Say we have an array num[2] and it has a range from 0-1 for example, it would print out something like 

00
01
11
10

If it were a simple permutation I could use a simple permutation function like this: 

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

but how do I make it go through a range of numbers of say n size with the given size of the array?

My question is different to another one here as I do not have a set array with what the values are, the example code does that but what I need is help with making print all the permutation of range n in an array of k spots, so say that n is 3 and k is 3 then it would be 

000
001
002
003
010
011
etc...

Upvotes: 0

Views: 2886

Answers (2)

AKJ88
AKJ88

Reputation: 733

Based on what you have asked, you want for each array with n elements and the resulting array with k elements, print all n^k permutations. So in each position i we have to put each element of the array and continue doing this for the next one. Something like this code:

void permute(int *array, int *result, int i, int n, int length) {
    if (length == i){
        printArray(result, length);
        return;
    }

    for (int j = 0; j < n; j++) {
        result[i] = array[j];
        permute(array, result, i + 1, n, length);
    }
}

int main()
{
    int a[] = { 0, 1, 2 }, b[2];
    permute(a, b, 0, 3, 2);
    return 0;
}

Upvotes: 1

Caleb
Caleb

Reputation: 124997

The idea is to generate the permutations of length n by concatenating each of the possible digits to each of the permutations of length n-1. So if you have digits 0-2 and you want to generate permutations of length 3, you first generate all the permutations of length 2, and then append or prepend the digits 0, 1, and 2 to each of those:

Permutations of length 2 are: 00, 01, 02, 10, 11, 12, 20, 21, 22

So permutations of length 3 are: 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200...

So, how do you generate all the permutations of length 2? You generate the permutations of length 1 and prepend each of your digits to all those permutations. How do you generate the permutations of length 1? There are no permutations of length 0, so you just list the digits.

Here's pseudocode:

permute(n, digits) {
    permutations = []
    smaller_permutations = permute(n-1, digits)
    for (i in digits) {
        if (length(smaller_permutation > 0) {
            for (j in smaller_permutations) {
                insert concatenate(i,j) into permutations
            }
        }
        else {
            insert i into permutations
        }
    }
    return permutations
}

Upvotes: 1

Related Questions