Generating Permutations in C++


Suppose you have the following set: {0,1,2}. How do you generate all the possible permutations of such set?

One possible approach is to use recursion. First we need to break the problem into smaller sub-problems. This could be done by splitting the set into two parts. We keep the right side fixed, and then find all the permutations of the left side, printing the whole set as we go along.

The key step is to swap the rightmost element with all the other elements, and then recursively call the permutation function on the subset on the left.

It might be easier to see it with some code, so below you’ll find a C++ implementation:

#include <iostream>

int array[10] = {0,1,2,3,4,5,6,7,8,9};

void swap(int x, int y){
    int temp = array[x];
    array[x]=array[y];
    array[y]=temp;

    return;
}

void printArray(int size){
    int i;

    for (i=0;i<size;i++)
        std::cout << array[i] << " ";

    std::cout << std::endl;

    return;
}

void permute(int k,int size){
    int i;

    if (k==0)
        printArray(size);
    else{
        for (i=k-1;i>=0;i--){
            swap(i,k-1);
            permute(k-1,size);
            swap(i,k-1);
        }
    }

    return;
}

int main(){

    permute(3,3);

    return 0;
}

On a future post I’ll talk about generating lexicographic permutations, so stay tuned.

2 thoughts on “Generating Permutations in C++

  1. Vinoth Anandan

    It was very useful for me to solve TCS codevita program

    IT was unique code which not found in other website

    Reply
  2. Theo

    Thank you very much for this algorithm. I used it in the UnrealEngine because they hav’nt implemented permutations yet.
    Great Work.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *