views:

250

answers:

5

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.

+15  A: 

See next_permutation

BlueRaja - Danny Pflughoeft
Good call (so to speak). Though to be fair, the OP did ask for the simplest *algorithm*.
benhoyt
+2  A: 

C++ STL has next_permutation for this purpose.

Neeraj
+7  A: 

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;
}
Bill
+1 for providing an example.
Thomas Matthews
There doesn't appear to be any point in the `bool` variable. You can just `do { ... } while (std::next_permutation(...));`
Charles Bailey
@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
@Bill: Fair enough. Personally, I find it clearer without the extra variable but perhaps that's just me.
Charles Bailey
A: 
George B.
A: 

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.

MSN