将移植函数从Python移植到C++

Question

我一直在使用来自堆栈溢出的算法：https://stackoverflow.com/a/9650593/4771889 也就是permute2（）函数。

为了我的目的，我改变了一些东西，它生成了我需要的正确数据。

这里是我的Python版本：

def permute(list, nextFixable, num, begin, end): 
    if end == begin + 1: 
     yield list 
    else: 
     for i in range(begin, end): 
      if nextFixable[list[i]] == num[i]: 
       nextFixable[list[i]] += 1 
       num[begin], num[i] = num[i], num[begin] 
       list[begin], list[i] = list[i], list[begin] 
       for p in permute(list, nextFixable, num, begin + 1, end): 
        yield p 
       list[begin], list[i] = list[i], list[begin] 
       num[begin], num[i] = num[i], num[begin] 
       nextFixable[list[i]] -= 1 


if __name__ == "__main__":  
    list = [0, 1, 2]   
    nextFixable = {0:0, 1:0, 2:0} 
    num = [0, 0, 0] 

    for p in permute(list, nextFixable, num, 0, len(list)): 
     print(p) 

我已经简化了使用一点点那里给一个基本的例子。

本实施例的输出是：

[0, 1, 2] 
[0, 2, 1] 
[1, 0, 2] 
[1, 2, 0] 
[2, 1, 0] 
[2, 0, 1] 

由于我的这个实际用途是较长的列表（未琐碎“0，1，2”）我很喜欢在这里所使用的发电机的功能（该产量报表）。

问题是Python很慢，我有时需要等几天才能得到结果。

我不是C++专家，但之前我发现C++比Python更快。所以你可以猜测我接下来做了什么 - 我试图用C++（Visual Studio 2015）重写它。

这就是我想出了：

#include "stdafx.h" 

#include <iostream> // for std::cout 
#include <vector> // for std::vector 
#include <map> // for std::map 

// https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/ 
#include <experimental/generator> 
using namespace std::experimental; 
using namespace std; 

using std::cout; 
using std::vector; 
using std::map; 

void print(vector<unsigned short> data) { 
    cout << "["; 
    for (unsigned short i = 0; i < data.size(); ++i) { 
     cout << (int)data[i]; 
     if (i < data.size() - 1) { 
      cout << ", "; 
     } 
    } 
    cout << "]\n"; 
} 

generator<vector<unsigned short>> permute(
    vector<unsigned short> list, 
    map<unsigned short, unsigned short> nextFixable, 
    vector<unsigned short> num, 
    unsigned short begin, 
    unsigned short end 
) { 
    if (end == begin + 1) { 
     __yield_value list; 
    } 
    else { 
     for (unsigned short i = begin; i < end; ++i) { 
      if (nextFixable[list[i]] == num[i]) { 
       nextFixable[list[i]]++; 
       swap(num[begin], num[i]); 
       swap(list[begin], list[i]); 
       for (auto p : permute(list, nextFixable, num, begin + 1, end)) { 
        __yield_value p; 
        swap(list[begin], list[i]); 
        swap(num[begin], num[i]); 
        nextFixable[list[i]]--; 
       } 
      } 
     } 
    } 
} 

int main() 
{ 
    vector<unsigned short> list = { 0, 1, 2 }; 
    map<unsigned short, unsigned short> nextFixable = { {0, 0}, {1, 0}, {2, 0} }; 
    vector<unsigned short> num = { 0, 0, 0 }; 

    for (auto p : permute(list, nextFixable, num, 0, (unsigned short)list.size())) { 
     print(p); 
    } 

    // Keep output window open. 
    std::getchar(); 
    return 0; 
} 

你可以看到我一直引用https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/ 这是给我带来__yield_value功能。 （我认为这是不可移植的，这对我来说最终确实会成为一个问题，因为我更喜欢在linux下运行这个工具，但对于一些早期的实验来说它确实有用。）

代码运行良好，但输出是：

[0, 1, 2] 
[0, 2, 1] 
[1, 2, 0] 
[2, 1, 0] 

让我们比较Python的输出 - 看来我们有两条线丢失：

[0, 1, 2] - Yes 
[0, 2, 1] - Yes 
[1, 0, 2] - Missing 
[1, 2, 0] - Yes 
[2, 1, 0] - Yes 
[2, 0, 1] - Missing 

通常在这一点上写一个SO问题，答案的从我不得不解释问题跳到我身上。在这种情况下，它没有。

这是可能的我做了一个不正确的语言假设，我没有知识来纠正自己。

因此，要解决这个问题 - 为什么我的端口从Python到C++的permute（）函数不能给我相同的输出？

Answer 1

我决定不睡觉，今晚并通过添加详细找到答案调试到两个版本的算法并研究它们的不同之处。

问题是这部分代码：粘贴Python代码为VS时，它有益一字排开的一切行动

 for (auto p : permute(list, nextFixable, num, begin + 1, end)) { 
      __yield_value p; 
     } 
     swap(list[begin], list[i]); 
     swap(num[begin], num[i]); 
     nextFixable[list[i]]--; 

可能，并感谢：

 for (auto p : permute(list, nextFixable, num, begin + 1, end)) { 
      __yield_value p; 
      swap(list[begin], list[i]); 
      swap(num[begin], num[i]); 
      nextFixable[list[i]]--; 
     } 

要匹配蟒蛇应该是到Python的方便缺乏大括号，再次比较代码时，这被忽视了。

这引发了第二个问题，其中nextFixable [whatever]会在一个无符号整数和溢出时递减到0以下 - 但这就是为什么。 （但是正如我在评论中指出的那样，我建议在do-while循环中使用std：next_permutation和std：sort结合使用，这个解决方案在一个简单的实验中已经被证明是关于5-D的，比这个算法快6倍。）

Answer 2

我会构建它是这样的（C++ 14）：

#include <iostream> 
#include <algorithm> 
#include <vector> 


// version which mutates the vector 
template<class Vec, class F> 
auto permute_over_inplace(Vec& vec, F&& f) 
{ 
    auto first = std::begin(vec); 
    auto last = std::end(vec); 

    // permutation reequires sorted ranges 
    if (not std::is_sorted(first, last)) { 
     std::sort(first, last); 
    } 

    // remove duplicates 
    last = vec.erase(std::unique(first, last), last); 

    // call the functor for each permutation 
    do { 
     f(vec); 
    } while (std::next_permutation(first, last)); 
}; 

// version which does not mutate the vector 
template<class Vec, class F> 
auto permute_over_copy(Vec vec, F&& f) 
{ 
    return permute_over_inplace(vec, std::forward<F>(f)); 
}; 



int main() 
{ 
    std::vector<int> list = {0, 1, 2}; 

    // an operation to perform on each permutation 
    auto print_list = [](auto&& c) 
    { 
     const char* sep = " "; 
     auto& os = std::cout; 

     os << "["; 
     for(auto&& item : c) { 
      os << sep << item; 
      sep = ", "; 
     } 
     os << " ]"; 
     os << "\n"; 
    }; 

    permute_over_copy(list, print_list); 

    list = { 9, 8, 7, 9, 6 }; 
    permute_over_inplace(list, print_list); 
} 

预期输出：

[ 0, 1, 2 ] 
[ 0, 2, 1 ] 
[ 1, 0, 2 ] 
[ 1, 2, 0 ] 
[ 2, 0, 1 ] 
[ 2, 1, 0 ] 

[ 6, 7, 8, 9 ] 
[ 6, 7, 9, 8 ] 
[ 6, 8, 7, 9 ] 
[ 6, 8, 9, 7 ] 
[ 6, 9, 7, 8 ] 
[ 6, 9, 8, 7 ] 
[ 7, 6, 8, 9 ] 
[ 7, 6, 9, 8 ] 
[ 7, 8, 6, 9 ] 
[ 7, 8, 9, 6 ] 
[ 7, 9, 6, 8 ] 
[ 7, 9, 8, 6 ] 
[ 8, 6, 7, 9 ] 
[ 8, 6, 9, 7 ] 
[ 8, 7, 6, 9 ] 
[ 8, 7, 9, 6 ] 
[ 8, 9, 6, 7 ] 
[ 8, 9, 7, 6 ] 
[ 9, 6, 7, 8 ] 
[ 9, 6, 8, 7 ] 
[ 9, 7, 6, 8 ] 
[ 9, 7, 8, 6 ] 
[ 9, 8, 6, 7 ] 
[ 9, 8, 7, 6 ]