生成所有具有订单约束的排列

-1

我试图在C++中实现一个解决以下问题的代码：给定自然数n和m对1和n之间的自然数，生成（在控制台中打印）全部置换从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; 
     } 
    } 

} 
}

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

来源

2017-09-29 Mr Peanutbutter

请在[SE代码审查]（https://codereview.stackexchange.com/）上改进工作代码请求。 – user0042

你可能会对[std :: next_permutation]感兴趣（http://en.cppreference.com/w/cpp/algorithm/next_permutation） –

@ user0042那么他并不需要改进这个代码，他需要一个更好的算法。这将成为话题。 – m69

这是怎么回事？

#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())); 
}

来源

2017-10-09 20:36:53

生成所有具有订单约束的排列

回答

相关问题