排列矢量

Question

我想要獲取矢量的每個排列，但也要用指示子排列的分隔符。看起來我的代碼中存在一個錯誤，因爲從我的結果中可以看到結尾的排列。

0 1 3 2 |和0 2 3 1 |和0 3 2 1 |都是重複的。

我也很好奇，如果有辦法做我想做的事，可以接受對矢量的引用而不是製作副本。

IDEONE：http://ideone.com/fork/2v0wk3

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

void permute(vector<int> v, int path_length) { 
    do { 
     for(int i=0; i<=3; ++i) { 
      cout << v[i] << " "; 
      if(i == path_length-1) 
      cout << "| "; 
     } 
     cout << endl; 

     if(path_length == v.size()) { 
      cout << "====="<< endl; 
      return; 
     } 

     permute(v, path_length+1); 
    } while(next_permutation(v.begin()+path_length-1,v.end())); 
} 

int main() { 
    vector<int> v; 

    for(int i=0;i<=3;++i) 
     v.push_back(i); 

    int path_length = 2; 
    permute(v, path_length); 
    return 0; 
} 

結果：

0 1 | 2 3 
0 1 2 | 3 
0 1 2 3 | 
===== 
0 1 3 | 2 
0 1 3 2 | 
===== 
0 1 | 3 2 
0 1 3 | 2 
0 1 3 2 | 
===== 
0 2 | 1 3 
0 2 1 | 3 
0 2 1 3 | 
===== 
0 2 3 | 1 
0 2 3 1 | 
===== 
0 2 | 3 1 
0 2 3 | 1 
0 2 3 1 | 
===== 
0 3 | 1 2 
0 3 1 | 2 
0 3 1 2 | 
===== 
0 3 2 | 1 
0 3 2 1 | 
===== 
0 3 | 2 1 
0 3 2 | 1 
0 3 2 1 | 
===== 

預期結果：

0 1 | 2 3 
0 1 2 | 3 
0 1 2 3 | 
===== 
0 1 3 | 2 
0 1 3 2 | 
===== 
0 2 | 1 3 
0 2 1 | 3 
0 2 1 3 | 
===== 
0 2 3 | 1 
0 2 3 1 | 
===== 
0 3 | 1 2 
0 3 1 | 2 
0 3 1 2 | 
===== 
0 3 2 | 1 
0 3 2 1 | 
===== 

Answer 1

考慮另一種方式來生成每次需要序列。 我們將有一個vector <int> cur來存儲當前序列，以及一個vector <bool> used來跟蹤哪些整數被使用，哪些不是。 在帶有depth自變量的遞歸函數中，找到另一個未使用的整數，將其作爲cur[depth]並繼續考慮下一個位置，即depth + 1。 深度處於所需範圍內時打印結果。

#include <iostream> 
#include <vector> 
using namespace std; 

int const n = 3; 

void generate (vector <int> & cur, vector <bool> & used, int depth) { 
    if (depth >= 2) { 
     for (int i = 0; i < depth; i++) { 
      cout << cur[i] << ' '; 
     } 
     cout << endl; 
    } 
    for (int i = 0; i <= n; i++) { 
     if (!used[i]) { 
      used[i] = true; 
      cur[depth] = i; 
      generate (cur, used, depth + 1); 
      used[i] = false; 
     } 
    } 
} 

int main() { 
    vector <int> cur (n); 
    vector <bool> used (n, false); 
    cur[0] = 0; 
    used[0] = true; 
    generate (cur, used, 1); 
    return 0; 
} 

，輸出是：

0 1 
0 1 2 
0 1 2 3 
0 1 3 
0 1 3 2 
0 2 
0 2 1 
0 2 1 3 
0 2 3 
0 2 3 1 
0 3 
0 3 1 
0 3 1 2 
0 3 2 
0 3 2 1 

您可以添加=====部分也一樣，如果你打印時depth > n。

Answer 2

你的問題對我來說不是很清楚。您可以使用不那麼出名next permutation從STL：

std::vector<int> my_vector = { 1 , 5 , 7 , 2 , 3 , 10}; 
std::sort(my_vector.begin(), my_vector.end()); 
do { 
    std::copy(my_vector.begin(), my_vector.end(), ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 
} while(std::next_permutation(my_vector.begin(), my_vector.end())); 

1 - 排序矢量 2 - 遍歷排列 （該做的，而只是複製到COUT打印）

我不是想你所謂的「sub」排列，你只是移動「|」每個置換內？