When you have a set of object, you may have to build all arrangement of those object.
Example, a vector
num = {0,1,2}, you want the 3! permutations ( {0,1,2}, {0,2,1}, {1,0,2},{1,2,0},{2,0,1},{2,1,0} )
Hopefully the Standard Template Library (STL) come with some useful function for that, but their behavior really depend of the operator you provide with your objects.
If you take a look at
next_permutation, it stands to "
Rearranges the elements in the range [first,last) into the next lexicographically greater permutation." but that point rely to the "bool operator( const T& elt)" of the object (class/type) you use.
A quick example of the pitfall in which I fall today. Imagine a type point define like below:
struct pos_t {
int x; int y;
pos_t(){x = 0 ; y = 0;}
pos_t(int X, int Y){x=X; y=Y;}
pos_t(pos_t const & r) {x = r.x; y=r.y;}
pos_t& operator=(pos_t const & r) {x = r.x; y=r.y; return *this;}
bool operator < ( pos_t const & p) const
{
return (x + y) < ( p.x+p.y);
}
friend ostream& operator << (ostream &o, const pos_t& p)
{
return o << "(" << p.x << "," << p.y << ")";
}
};
Now using the following list of point, (1,3) ,(2,2) , (3,0) ,(3,1), you expect to get 24 permutations. But you will not !!!! The reason is the
operator < we define in our
class/struct. Using that operator (1,3) is similar to (3,1) and that the reason why when using next_permutation we implicitly use the
less-than operator and we fail.
To really get all permutation out-of
next_permutation we need to define clear compare operator.
bool operator < ( pos_t const & p) const
{
return (x < p.x) || ((x == p.x) && (y < p.y));
}
Now using our list of 4 points, we can call a simple loop to store and display all permutations. See below a piece of code extract of Coding Challenge call "Treasure Hunter" (a kind of A* algorithm can be use to solve it .... )
deque<vector<pos_t>> treasure_order;
std::sort(begin(treasurePos), end(treasurePos));
do {
vector<pos_t> c;
c.push_back(pos_t(0,0));
copy(begin(treasurePos), end(treasurePos), back_inserter(c));
c.push_back(pos_t(maze.size()-1, maze.size()-1));
copy(begin(c), end(c), ostream_iterator<pos_t>(cout, " -> "));
cout << endl;
treasure_order.push_back(c);
} while ( std::next_permutation(begin(treasurePos),end(treasurePos)) );//*/
cout << "we stored " << treasure_order.size() << " path to get all the treasure (=nbTreasure! = " << fact((int)treasurePos.size()) << ")" << endl;
Using that simple 2D maze where * mark treasure position:
. . . .
. # . *
. # * .
* * # .
We now that based on the 4 treasure we have, we can visit those 4 position using 24 different order....
Remark, here all list start and end with the same point (top-left and bottom-right corner) because they are the starting and ending point of th "Treasure Hunt" !
(0,0) -> (1,3) -> (2,2) -> (3,0) -> (3,1) -> (3,3) ->
(0,0) -> (1,3) -> (2,2) -> (3,1) -> (3,0) -> (3,3) ->
(0,0) -> (1,3) -> (3,0) -> (2,2) -> (3,1) -> (3,3) ->
(0,0) -> (1,3) -> (3,0) -> (3,1) -> (2,2) -> (3,3) ->
(0,0) -> (1,3) -> (3,1) -> (2,2) -> (3,0) -> (3,3) ->
(0,0) -> (1,3) -> (3,1) -> (3,0) -> (2,2) -> (3,3) ->
(0,0) -> (2,2) -> (1,3) -> (3,0) -> (3,1) -> (3,3) ->
(0,0) -> (2,2) -> (1,3) -> (3,1) -> (3,0) -> (3,3) ->
(0,0) -> (2,2) -> (3,0) -> (1,3) -> (3,1) -> (3,3) ->
(0,0) -> (2,2) -> (3,0) -> (3,1) -> (1,3) -> (3,3) ->
(0,0) -> (2,2) -> (3,1) -> (1,3) -> (3,0) -> (3,3) ->
(0,0) -> (2,2) -> (3,1) -> (3,0) -> (1,3) -> (3,3) ->
(0,0) -> (3,0) -> (1,3) -> (2,2) -> (3,1) -> (3,3) ->
(0,0) -> (3,0) -> (1,3) -> (3,1) -> (2,2) -> (3,3) ->
(0,0) -> (3,0) -> (2,2) -> (1,3) -> (3,1) -> (3,3) ->
(0,0) -> (3,0) -> (2,2) -> (3,1) -> (1,3) -> (3,3) ->
(0,0) -> (3,0) -> (3,1) -> (1,3) -> (2,2) -> (3,3) ->
(0,0) -> (3,0) -> (3,1) -> (2,2) -> (1,3) -> (3,3) ->
(0,0) -> (3,1) -> (1,3) -> (2,2) -> (3,0) -> (3,3) ->
(0,0) -> (3,1) -> (1,3) -> (3,0) -> (2,2) -> (3,3) ->
(0,0) -> (3,1) -> (2,2) -> (1,3) -> (3,0) -> (3,3) ->
(0,0) -> (3,1) -> (2,2) -> (3,0) -> (1,3) -> (3,3) ->
(0,0) -> (3,1) -> (3,0) -> (1,3) -> (2,2) -> (3,3) ->
(0,0) -> (3,1) -> (3,0) -> (2,2) -> (1,3) -> (3,3) ->
a shortcut will be welcome !
