find all permutations

[Gunnar G]

Hello.
Given vector<double> x;
where I have no knowledge of the size of x at compile time, how can I write
code that will give me all the possible permutations of the elements in the
vector x?

For each permutation I get, I must temporarily save it in a vector and do
something with the vector, and then scrap it, and create the next
permutation.

How do I do this in an efficient way?

In the small case (the number of elements in x is small) it is possible to
store all permutations in a new vector, if that would be of any help.

 

[Alf P. Steinbach]

* Gunnar G:

Given vector<double> x;
where I have no knowledge of the size of x at compile time, how can I write
code that will give me all the possible permutations of the elements in the
vector x?

For each permutation I get, I must temporarily save it in a vector and do
something with the vector, and then scrap it, and create the next
permutation.

How do I do this in an efficient way?

In the small case (the number of elements in x is small) it is possible to
store all permutations in a new vector, if that would be of any help.

Sort the vector (std::sort) and use std::next_permutation or whatever it's
called -- check it out, presumably in <algorithm>.

If you can have duplicate elements it might be an idea to instead create
a vector with elements 1, 2, 3 and so forth, generate permutations of that
vector, and use the element values as indices to the original vector.

 

[Kai-Uwe Bux]

Hello.
Given vector<double> x;
where I have no knowledge of the size of x at compile time, how can I
write code that will give me all the possible permutations of the elements
in the vector x?

For each permutation I get, I must temporarily save it in a vector and do
something with the vector, and then scrap it, and create the next
permutation.

How do I do this in an efficient way?

In the small case (the number of elements in x is small) it is possible to
store all permutations in a new vector, if that would be of any help.

The idiom I use for processing all permutations goes like this:

#include <algorithm>

std::sort( x.begin(), x.end() );
do {
// whatever you want, but don't change the order in x.
} while ( std::next_permutation( x.begin(), x.end() ) );


Best

Kai-Uwe Bux