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.