將移植函數從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 ]