c++ - 繰り返しのない複数のベクトル要素の組み合わせ

Question

n 個のベクトル、たとえば 3 個のベクトルがあり、n 個の要素があります (必ずしも同じ量である必要はありません)。それらの間でx個の組み合わせを選択する必要があります。ベクトル[n]から2つを選択するように。例：

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

v1[0] と v1[1] のように、1 つのベクトル自体から組み合わせることはできません。これどうやってするの？私はすべてを試しましたが、これを理解できません。

Answer 1

あなたが正しく理解していれば、それぞれが異なる数の要素 (i 番目のベクトル Si のサイズと呼びます) を持つ N 個のベクトルがあり、繰り返しなしでこれらのベクトルから M 個の要素の組み合わせを選択する必要があります。各組み合わせは、各ベクトルから 1 つの要素である 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];
}

これは基本的に、1D 配列として表される 2D 配列にインデックスを付けるときと同じように、各インデックスのチャンクに m を分割します。

N=3 の例を取ると、次の順列の 3 つの要素を取得できます。

v1[指数[0]] v2[指数[1]] v3[指数[2]]

必要な数の m の異なる値を生成します。

Answer 2

おそらく、問題の不適切な定義から混乱が生じます。V ベクトルの 1 つから 1 つの要素を N 回選択する必要があると推測すると、次のように実行できます。

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.