Calculate all possible and meaningful permutations

Question

My problem is some kind of the Chinese postman problem.

I got a maze in which the program puts n agents and n targets. Now every agent has to visit every target at least once. Therefore I have to calculate the shortest path between all targets using the A* algorithm, maybe later the D*.

Now my problem is to calculate the permutations of the targets. I mean I have a program which calculates all possible permutations. But this doesn't mean it's clever to know them all. I mean if I have 4 targets, I got n! permutations (in this example 24). But the permutation 1234 got the same path length as 4321. So I need to upgrade my function to find symmetries in all permutations, and just use the A* for the minimum number of permutations.

So this is the code I currently use to generate all permutations. Currently I just print them out, but later i want to sore the permutations in a kind of array or vector, but that's rather simple compared to my main problem.

#include <iostream>
#include <algorithm>
#include <iterator>

int main( int argc, char *argv[] )
{
  unsigned int n = atoi( argv[1] );
  unsigned int f[n], *const fn = f + sizeof(f) / sizeof(*f);

  for(int j=0; j<n; j++)
  {
    f[j]=(j+1);
  }

  unsigned int i = 0;

  do
  {
    std::cout << ++i << ". Permutation: ";
    copy(f, fn, std::ostream_iterator<int>(std::cout, " "));;
    std::cout << std::endl;
  }
  while(std::next_permutation(f, fn));

  return 0;
}

Answer 1

To skip symmetrical permutations, you may skip the one where the last node is inferior to first node:

void show_permutation(std::vector<unsigned int> v)
{
    int i = 0;
    do {
        if (v.back() < v.front()) {
            continue;
        }
        std::cout << ++i << ". Permutation: ";
        copy(v.begin(), v.end(), std::ostream_iterator<unsigned int>(std::cout, " "));
        std::cout << std::endl;
    } while(std::next_permutation(v.begin(), v.end()));
}

Live example