如果我們從每個Y向量中選擇一個值，則每個X數字組合都有可能

Question

如果存在此問題的正式名稱（或者這是重複的並且我沒有找到正確的問題來查看），那麼指出我真正應該尋找的東西也將不勝感激！但是，我一直無法找到任何有關這個特定問題的討論或方法。

我試圖讓問題儘可能簡單，如果更多的細節將有助於讓我知道。

假設我們有INT的4個隨機長度載體：

std::vector<int> v1 {1, 7, 5, 2}; 
std::vector<int> v2 {4, 2, 1}; 
std::vector<int> v3 {1, 9, 4, 6, 4, 1, 2}; 
std::vector<int> v4 {9, 4}; 

在這些四個矢量的，我需要生成，我們選擇從每個源向量僅使用一個INT每個可能的組合（V1 - V4）在一次。結果應該是我們從源向量中生成每個可能的N長度數，其中N =源向量的數量（在這種情況下爲4）。

幾個可能的組合是很容易產生，例如只選擇第一數目從每個源向量的：

1 4 1 9 

選擇每個源向量的最後一個號碼：

2 1 2 4 

我被卡住的地方正在產生每一個可能的組合。我需要每個可能的N長度數字，可以通過組合來自4個源矢量中的每一個的一個int來創建。

謝謝！

Answer 1

你確實描述了你的套件的Cartesian product。就像一個普通的數字產品一樣，這是對兩件事情的一種操作，但它可以連續地應用於兩件事情：

A x B x C x D = A x（B x（C x D ））

該結構是理解問題的關鍵。您可以將其分解爲遞歸子問題，每個問題只涉及兩組。這樣你可以處理任意數量的集合。

解決問題的程序也可以遞歸，也可以迭代。接下來是使用由vector<int>表示的集合的lists的半優化遞歸解決方案。鑑於集列表

A，...

它計算的兩件事情笛卡爾乘積：A，以及集的其餘部分的笛卡爾乘積：

一個x（...）

您可以重新安排這個過程，以基本情況開始並向上，即（（D x C）x B）x A.這樣，您可以使用循環rath呃比遞歸調用。但考慮問題的遞歸結構是組織思想的好方法。

void cartesian_product(list< vector<int> > sets, list< vector<int> >& product) { 
     if (sets.empty()) 
       return; 

     // get first set 
     auto& s = sets.front(); 

     // base case 
     if (++begin(sets) == end(sets)) { 
       for (auto k : s) { 
         product.push_back({ k }); 
       } 
       return; 
     } 

     // get cartesian product of the rest of the sets 
     cartesian_product(list< vector<int> >(++begin(sets), end(sets)), product); 

     // make additional copies of product and append each element of first set to them 
     list< vector<int> > additions; 
     for (auto k = ++begin(s); k != end(s); ++k) { 
       list< vector<int> > ad = product; 
       for (auto& x : ad) { 
         x.push_back(*k); 
       } 
       additions.splice(end(additions), ad); 
     } 

     // append the first element of the first set to the original product 
     for (auto& x : product) { 
       x.push_back(s.front()); 
     } 

     // append the additions to the final product 
     product.splice(end(product), additions); 

     return; 
} 

---

下面是程序的其餘部分：

#include <cassert> 
#include <iostream> 
#include <list> 
#include <vector> 

using std::vector; 
using std::list; 
using std::cout; 
using std::endl; 

void cartesian_product(list< vector<int> > sets, list< vector<int> > &product); 

int main(int argc, char *argv[]) { 
     list< vector<int> > sets = { 
       {1, 7, 5, 2}, 
       {4, 2, 1}, 
       {1, 9, 4, 6, 4, 1, 2}, 
       {9, 4} 
     }; 

     list< vector<int> > product; 
     cartesian_product(sets, product); 

     for (auto& x : product) { 
       cout << "{ "; 
       for (auto k : x) { 
         cout << k << " "; 
       } 
       cout << "}" << endl; 
     } 
} 

Answer 2

這裏是與輸入矢量的任意量的答案：

參見索引的結構爲多個，在不同編號系統的數字組成。 然後考慮計算一組索引，就像在一些數字系統中計算一個常規數字一樣。 例如，對於尺寸爲3 5 2 5的四個向量，索引集合0 2 1 4將導致0 3 0 0。

對於下面的代碼，我假設你的載體的另一種載體內給予，這是因爲vector<vector<int> >

這裏與指數類：

class Indices { 

private: 
    vector<size_t> indices; 
    vector<size_t> maximal_sizes; 
    bool _max_reached; 

public: 

    Indices(const vector<vector<int> >& vectors) : indices(vectors.size(), 0), maximal_sizes(vectors.size()), _max_reached(false) { 

     for(size_t i = 0; i < vectors.size(); i++){ 
      maximal_sizes[i] = vectors[i].size(); 
     } 
    } 

    const size_t& operator[] (const size_t i) const { return indices[i]; } 
    bool max_reached() const { return max_reached; } 

    void count_up() { 

     size_t current = 0; 
     while(current < indices.size()){ 
      indices[current]++; 
      if(indices[current] >= maximal_sizes[current]){ 
       indices[current] = 0; 
       current++; 
      } else { 
       return; 
      } 
     } 
     _max_reached = true; 
    } 

} 

（分成頭這一點，源）

和使用它像

inline void print(const vector<vector<int> >& vectors, const Indices& indices){ 

    for(size_t i = 0; i < vectors.size(); i++){ 
     cout << vectors[i][Indices[i]] << " "; 
    } 
    cout << endl; 
} 

void all_combinations(const vector<vector<int> >& vectors){ 

    Indices indices(vectors); 

    while(not indices.max_reached()){ 
     print(vectors, indices); 
     indices.count_up(); 
    } 
} 

（可能不是完全是這樣的功能，但你明白了。另外，Indices對我而言並不足以描述，但現在無法想到一個好的短名稱。 max_reached技工有點煩人，看起來不夠優雅。如果有人有改進這個想法，我很樂意聽到。）