permutations algorithm

Question

This is for a class so please don't be too specific, but I am looking for a way to list all permutations of an array of digits.

We have to arrange different numbers on different pillars (like a lock) to unlock a combination. There may be 6 numbers on each of the 4 pillars. But it should work for any n on r as long as n>r.

I have the way to randomly generate a combination, and methodically look for it in a list but I am having trouble producing an algorithm to generate all permutations.

I am able to get all combinations for digits 1-6 using this in C++:

//n = number of digits - 1; list = list of digits to work with; 
//number=finalized list of digits
void permute(int n, vector<int> list, vector<vector<int>>* number)
{
    if(n==1)
    {
        number->push_back(list);

    }else
    {
        for(int i = 1;i<n;i++)
        {
            permute(n-1,list, number);
            if(n%2 == 0)
            {
                swap(list[1],list[n]);
            }else
            {
                swap(list[i],list[n]);
            }
        }
    }

};

But then i get a list such as 123456 163452 etc where 1 is always the first digit but I need to also obtain when the first digit is switched around and only 4 digits are present.

example

6341

4163

etc where there are 4 digits that range from 1-6 and you have all possible combinations.

Can anyone point me in the right direction for another algorithm to supplement this or so?

Answer 1

C++ offers a perfect solution for this - it's std::next_permutation (you need to include <algorithms> to use it).

vector<int> list;
std::sort(list.begin(), list.end());
do {
    // use the current permutation of the list
} while (std::next_permutation(list.begin(), list.end()));

An important point to remember about this function is that if you would like to go through all permutations of a range, the range must be sorted before you make the first call to next_permuration, otherwise you are going to stop before exhausting all permutations.