2D矢量（笛卡爾乘積）中元素的所有排列

這是我一直堅持的一小部分，它是一個更大的任務的一部分。2D矢量（笛卡爾乘積）中元素的所有排列

我有一個2D向量，例如：

v1: 0 1 2 3 4 
v2: 0 1 2 
v3: 0 1 2 3 4 
v4: 0 1 2 3 
v5: 0 1 2 3 4

（每行是一個向量）

我需要找到所有的排列，選擇從各行的一個元素。正如有人指出的那樣，這將是笛卡兒的產品。
我試過使用循環，但那隻會在一個方向上工作（它錯過了很多排列組合）
我也查看了next_permutation，但我不確定是否可以將它應用於2D矢量。

此外，行數不是靜態的，所以我不能嵌套5個循環，因爲根據條件可能會有更多或更少的行。

有沒有辦法做到這一點？

來源

2012-06-18 SamTheSammich

[數組上的Perfoming Cartesian產品]可能的副本（http://stackoverflow.com/questions/10840430/perfoming-cartesian-product-on-arrays） – templatetypedef

您在尋找的不是子集，而是笛卡爾積（從每個元素中挑選一個元素的所有方法）。 – templatetypedef

@templatetypedef啊，我改正了標題。謝謝 – SamTheSammich

我只是寫出一個可能的答案，這不是非常有效，但應該是可用的。

請注意，我假設（在你的例子），你希望所有的5元組，從V1拍攝的第一要素，從V2拍攝的第二要素，第三從V3等

void gen_all (
    vector<vector<int> > & output_perms, 
    vector<vector<int> > const & input, 
    vector<int> & cur_perm, 
    unsigned cur_row = 0 
) 
{ 
    if (cur_row >= input.size()) 
    { 
    // This is where you have found a new permutation. 
    // Do whatever you want with it. 
    output_perms.push_back (cur_perm); 
    return; 
    } 

    for (unsigned i = 0; i < input[cur_row].size(); ++i) 
    { 
    cur_perm.push_back (input[cur_row][i]); 
    gen_all (output_perms, input, cur_perm, cur_row + 1); 
    cur_perm.pop_back(); 
    } 
}

這樣調用上面的函數：（假設v握着你的原套）

vector<vector<int> > output; 
vector<int> temp; 
gen_all (output, v, temp);

正如我之前說的，有更有效和優雅的方式，和上面的代碼可能甚至不編譯（我只是寫這裏）。

來源

2012-06-18 22:18:52 yzt

這個問題被標記爲「家庭作業」。這是否意味着我不應該在代碼中發佈解決方案？ – yzt

我確實發現了一個遞歸的笛卡爾積函數，這個函數給了我一個好看的地方。不幸的是，事實證明，我看問題的整個方法是低效的，我應該使用回溯。感謝解決方案，但它比其他一些嘗試更容易理解。 – SamTheSammich

std::next_permutation只適用於一組迭代器。它不保留任何靜態內存，它都基於迭代器的當前狀態。這意味着您一次可以在多個矢量上使用它。不要試圖一次排列整個結構。

來源

2012-06-18 22:11:50

2D矢量（笛卡爾乘積）中元素的所有排列

回答

相關問題