c++ - 置换 vector

Question

我正在尝试获取 vector 的每个排列，但也有一个指示子排列的分隔符。从我的结果中可以看出，我的代码似乎有一个错误，即结束排列。

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

我也很好奇是否有一种方法可以做我想做的事情，它可以接受对 vector 的引用而不是制作拷贝。

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 时打印它.