多重向量的元素的組合不重複

Question

我有n個向量，比如說3，它們有n個元素（不一定是相同的數量）。我需要選擇它們之間的x組合量。像從載體[n]中選擇2一樣。 實施例：

std::vector<int> v1(3), v2(5), v3(2); 

從一個載體本身不能有組合，如V1 [0]和V1 [1]。我怎樣才能做到這一點？ 我試過了一切，但無法弄清楚這一點。

Answer 1

如果我理解正確你有N個矢量，每個具有不同數量的元素（呼叫的大小第i個矢量Si）和你從這些矢量中選擇M個元素的組合而不重複。每個組合都是N個元素，每個矢量都有一個元素。

在這種情況下可能的排列的數量是矢量的大小，的產品，該產品由於缺乏某種形式的方程的設定我打電話P和用C計算++：

std::vector<size_t> S(N); 
// ...populate S... 
size_t P = 1; 
for(size_t i=0;i<S.size();++i) 
    P *= S[i]; 

所以現在問題變成從0到P-1之間選取M個不同的數字，然後將這些M個數字中的每一個轉換成N個索引爲原始向量。我可以想出幾種計算這些M數字的方法，也許最簡單的方法是繼續繪製隨機數，直到獲得M個不同的數（有效地拒絕分佈採樣）。

稍微更復雜的部分是將你的M個數字轉換成一個索引向量。我們可以像你將索引表示爲一維數組的二維數組時

size_t m = /* ... one of the M permutations */; 
std::vector<size_t> indices_m(N); 

for(size_t i=0; i<N; ++i) 
{ 
    indices[i] = m % S[i]; 
    m /= S[i]; 
} 

基本上扒m，最高成塊爲每指數做到這一點。

現在，如果我們把你的N = 3例子中，我們可以得到我們排列的3個元素與

V1 [指數[0] V2 [指數[1] V3 [指數[2]

根據需要生成m個不同的m值。

Answer 2

可能由於對問題的定義不正確而引起混淆。猜測需要N次挑1個元件從V矢量的1，則可以做到這一點：

select N of the V vectors you want to pick from (N <= V) 
for each of the selected vectors, select 1 of the vector.size() elements.