C++ algorithm for N! orderings

I have a list of N items and I am wondering how I can loop through the list to get every co开发者_运维问答mbination. 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 std::next_permutation   

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;
}

C++ STL has next_permutation for this purpose.

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!

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.