计算所有可能的和有意义的排列

Question

我的问题是某种中国邮递员问题。

我得到了一个迷宫，其中程序放置n个代理和n个目标。现在每个代理都必须至少访问一次目标。因此，我必须使用A *算法来计算所有目标之间的最短路径，也许后面是D *。

现在我的问题是计算目标的排列。我的意思是我有一个计算所有可能的排列的程序。但这并不意味着全部了解它们是很聪明的。我的意思是如果我有4个目标，我得到n！排列（在本例中为24）。但是排列1234的路径长度与4321相同。所以我需要升级我的函数来找到所有排列中的对称性，并且只用A *来表示最小排列数。

所以这是我目前用来生成所有排列的代码。目前我只是将它们打印出来，但后来我想用一种数组或矢量来排列排列，但与我的主要问题相比，这非常简单。

#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

要跳过对称排列，可以跳过所述一个其中最后节点是劣于第一节点：

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