計算所有可能的和有意義的排列

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