順序制約付きすべての順列を生成する

Question

次の問題を解決するコードをC++で実装しようとしています。自然数nと1からnまでのm組の自然数を指定すると、generate（コンソールに出力）all置換の第2の要素の前に各対の第1の要素が現れるように、1からnまでの順列。

私が今までに書いたコードは、1からnまでのすべての順列を生成するための標準アルゴリズムから採用した単純なバックトラッキングアルゴリズムです。

Mは、行M [j]が、それらの前にjがなければならないようなすべての数字を含む行列であり、Nは、N [j]が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())); 
}