多重向量的元素的组合不重复

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.