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

This function lists all permutations using bitset

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

const int N = 3;

void permute(string_view s, bitset<N> &mask, string &pref)
{
    if (mask.all()) {
        cout << pref << endl;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!mask[i]) {
            mask.set(i);
            pref.push_back(s[i]);
            permute(s, mask, pref);
            pref.pop_back();
            mask.reset(i);
        }
    }
}

int main()
{
    string pref;
    bitset<N> mask;
    permute(string("abc"), mask, pref);
    return 0;
}

and with a few modifications, it prints all combinations

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

const int N = 3;
const int M = 2;

void permute(string_view s, bitset<N> &mask, string &pref)
{
    if (pref.size() == M) {
        cout << pref << endl;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!mask[i]) {
            mask.set(i);
            permute(s, mask, pref);
            pref.push_back(s[i]);
            permute(s, mask, pref);
            pref.pop_back();
            mask.reset(i);
            break;
        }
    }
}

int main()
{
    string pref;
    bitset<N> mask;
    permute(string("abc"), mask, pref);
    return 0;
}

Answer 2

First of All, let's talk your question to print all the P(6,4) array in set {1,2,3,4,5,6}, but std::next_permutation will only adapt for the permutation of all the element (P(6,6)), not suitable for your issue (P(6,4)). I think use std::next_permutation can get the combination very easily, and since we know P(6,4)=C(6,4)*P(4,4), the simple code implementation maybe like this:

 1 #include <iostream>
  2 #include <vector>
  3
  4 int main()
  5 {
  6     std::vector<int> list;
  7     std::vector<int> subList;
  8     std::vector<bool> flag;
  9
 10     for (int i=1; i<=6; ++i)
 11         list.push_back(i);
 12     flag.insert(flag.end(),4,1);
 13     flag.insert(flag.end(),2,0);
 14     std::sort(flag.begin(), flag.end());
 15     do
 16     {
 17         subList.clear();
 18         for(int i=0; i<flag.size(); ++i)
 19         {
 20             if(flag[i])
 21             {
 22                 subList.push_back(list[i]);
 23             }
 24         }
 25         do
 26         {
 27             for(std::vector<int>::iterator it=subList.begin(); it!=subList.end(); ++it)
 28             {
 29                 std::cout << *it << " ";
 30             }
 31             std::cout << std::endl;
 32         }while(std::next_permutation(subList.begin(), subList.end()));
 33         std::cout << std::endl;
 34     } while(std::next_permutation(flag.begin(), flag.end()));
 35     return 0;
 36 }

That's obviously the out loop look for C(6,4), and the inner loop look for P(4,4). Didn't take much time on your code, for combination, you can use search method just like DFS, refer: combinations of

Answer 3

A general algorithm for recursively generating permutations of N-length from a list of N items is:

For each element x in list

Make a copy of list without element x; call it newList Find all of the permutations of newList (thats the recursion, btw)

Add element x to the beginning of each permutation of newList

#include <iostream>
#include <list>

typedef std::list<int> IntList;
void iterlist(IntList& lst)
{
    for (IntList::iterator it=lst.begin(); it!=lst.end(); it++)
        cout << " " << *it;
    cout << endl;
}

std::list<IntList> permute(IntList& L1)
{
    if (L1.size() == 1)
        return std::list<IntList>(1,L1);

    std::list<IntList> res;
    for (IntList::iterator i = L1.begin(); i != L1.end();)
    {
        // remember this
        int x = (*i);

        // make a list without the current element
        IntList tmp(L1.begin(), i++);
        tmp.insert(tmp.end(), i, L1.end());

        // recurse to get all sub-permutations
        std::list<IntList> sub = permute(tmp);

        // amend sub-permutations by adding the element
        for (std::list<IntList>::iterator j=sub.begin(); j!=sub.end();j++)
            (*j).push_front(x);

        // finally append modified results to our running collection.
        res.insert(res.begin(), sub.begin(), sub.end());
    }
    return res;
}

int main()
{
    IntList lst;
    for (int i=0;i<4;i++)
        lst.push_back(i);
    std::list<IntList> res = permute(lst);
    for (std::list<IntList>::iterator i=res.begin(); i!=res.end(); i++)
        iterlist(*i);
    return 0;
}

Answer 4

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.

Answer 5

If you need to implement your own, this may be no help, but C++ has next_permutation built-in.

http://www.cplusplus.com/reference/algorithm/next_permutation/

The algorithm behind this function is explained here: std::next_permutation Implementation Explanation