C++ algorithm for N! orderings

Question

I have a list of N items and I am wondering how I can loop through the list to get every combination. There are no doubles, so I need to get all N! orderings. Extra memory is no problem, I'm trying to think of the simplest algorithm but I'm having trouble.

See also an explanation of two different algorithms at http://stackoverflow.com/questions/352203/generating-permutations-lazily/ — ShreevatsaR, Jul 13 '10 at 13:08

score 16 · Accepted Answer · edited Sep 26 '13 at 06:13

16

See std::next_permutation

edited Sep 26 '13 at 06:13

answered Jan 26 '10 at 19:19

BlueRaja - Danny Pflughoeft

84,206
33
197
283

1

Good call (so to speak). Though to be fair, the OP did ask for the simplest *algorithm*. – Ben Hoyt Jan 27 '10 at 02:22

score 8 · Answer 2 · answered Jan 26 '10 at 19:36

8

Expanding on others' answers, here's an example of std::next_permutation adapted from cplusplus.com

#include <iostream>
#include <algorithm>
using namespace std;

void outputArray(int* array, int size)
{
  for (int i = 0; i < size; ++i) { cout << array[i] << " "; }
}

int main ()
{
  int myints[] = { 1, 2, 3, 4, 5 };
  const int size = sizeof(myints);

  cout << "The 5! possible permutations with 5 elements:\n";

  sort (myints, myints + size);

  bool hasMorePermutations = true;
  do
  {
    outputArray(myints, size);
    hasMorePermutations = next_permutation(myints, myints + size);
  }
  while (hasMorePermutations);

  return 0;
}

answered Jan 26 '10 at 19:36

Bill

14,257
4
43
55

There doesn't appear to be any point in the `bool` variable. You can just `do { ... } while (std::next_permutation(...));` – CB Bailey Jan 26 '10 at 22:03
1

@Charles: It's true, I could do that. For teaching purposes I pulled out the next_permutation since that was the focus of the code. – Bill Jan 26 '10 at 22:18
Fair enough. Personally, I find it clearer without the extra variable but perhaps that's just me. – CB Bailey Jan 26 '10 at 22:28

score 2 · Answer 3 · answered Jan 26 '10 at 19:21

2

C++ STL has next_permutation for this purpose.

answered Jan 26 '10 at 19:21

sud03r

19,109
16
77
96

score 0 · Answer 4 · answered Jan 26 '10 at 20:36

Simple algorithm using Recursion:

PSEUDOCODE

getPermutations(CurItemList , CurPermList)

if CurItemList.isempty()
    return CurPermList
else
    Permutations = {}

    for i = 1 to CurItemList.size() 
        CurPermList.addLast(CurItemList.get(i))

        NextItemList = CurItemList.copy()
        NextItemList.remove(i)

        Permutations.add(getPermutations(NextItemList, CurPermList))

        CurPermList.removeLast()


return Permutations

// To make it look better
Permutations(ItemList) 
    return getPermutations(ItemList, {})

I didnt test it, but should work. Maybe its not the smartest way to do it, but its an easy way. If something is wrong please let me know!

score 0 · Answer 5 · answered Jan 26 '10 at 22:00

Try building up the set of combinations recursively with a fixed count of possible elements. The set of all possible combinations will be the union of the sets of combinations of 1 element, 2 elements, ... up to N elements.

Then you can attack each fixed sized combination individually.

C++ algorithm for N! orderings

5 Answers5

Linked