生成具有顺序约束的所有排列

Question

我正在尝试用 C++ 实现一个代码来解决以下问题：给定一个自然数 n，以及 1 和 n 之间的 m 对自然数，生成（在控制台中打印）1 的所有排列到 n 使得每对的第一个元素出现在排列中的第二个元素之前。

到目前为止我写的代码是一个简单的回溯算法，我从标准算法改编而来，用于生成从 1 到 n 的所有排列。

在下面的代码中，M 是一个矩阵，使得行 M[j] 包含所有数字，使得 j 必须在它们之前，而 N 是一个矩阵，使得 N[j] 包含所有数字，使得我必须去追他们。此外，"used" 向量会跟踪我已经使用过的元素。

void f(int i){
if (i == n) return print();

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

else {
    for (int j = 0; j < n; ++j){

    bool aux = true;
    int k = 0;
    while (aux and k < M[j].size()){
        if (used[M[j][k]]) aux = false;
        ++k;
    }
    k = 0;
    while (aux and k < N[j].size()){
        if (not used[N[j][k]]) aux = false;
        ++k;
    }

    if (aux){
        if (not used[j]){
            V[i] = j;
            used[j] = 1;
            f(i+1);
            used[j] = 0;
        }
    }

}
}

问题是这段代码太慢了。所以我想问问你们有没有办法让它更快。

Answer 1

这个呢？

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>


using namespace std;

int main()
{
    vector<pair<int,int>> m={{1,2},{4,3}};
    vector<int> arr={1,2,3,4,5};

    do
    {
        if (all_of(m.begin(),m.end(),[&](pair<int,int>& p)
            {
                auto it1 = find(arr.begin(),arr.end(),p.first);
                auto it2 = find(arr.begin(),arr.end(),p.second);
                return (it1 != arr.end() && it2 != arr.end() && it1 <= it2);
            }))
        {
            for(auto it: arr)
                cout<<it<<" ";
            cout<<endl;
        }
    }while(std::next_permutation(arr.begin(),arr.end()));
}

生成具有顺序约束的所有排列

Generating all permutations with order constraints

c++

algorithm

backtracking