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.
Good call (so to speak). Though to be fair, the OP did ask for the simplest *algorithm*.
benhoyt
2010-01-27 02:22:21
+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
2010-01-26 19:36:21
There doesn't appear to be any point in the `bool` variable. You can just `do { ... } while (std::next_permutation(...));`
Charles Bailey
2010-01-26 22:03:20
@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
2010-01-26 22:18:54
@Bill: Fair enough. Personally, I find it clearer without the extra variable but perhaps that's just me.
Charles Bailey
2010-01-26 22:28:57
A:
George B.
2010-01-26 20:36:05
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
2010-01-26 22:00:49