2

一意の値のみを持つベクトルがあり、すべてのペアを生成したいとします。そのためのアルゴリズムは次のとおりです。

vector< int > data;
// ... pushback some data

vector< vector< int > > pairs;

for( size_t i = 0; i < data.size() - 1; ++i )
{
    for( size_t j = i + 1; j < data.size(); ++j )
    {
        vector< int > pair; 
        pair.push_back( data[i] ); 
        pair.push_back( data[j] );

        pairs.push_back( pair );
    }
}

ここで、トリプルの場合、アルゴリズムは次のように変更されます。

vector< int > data;
// ... pushback some data

vector< vector< int > > triples;

for( size_t i = 0; i < data.size() - 2; ++i )
{
    for( size_t j = i + 1; j < data.size() - 1; ++j )
    {
        for( size_t k = j + 1; k < data.size(); ++k )
        {
            vector< int > triple; 
            triple.push_back( data[i] ); 
            triple.push_back( data[j] );
            triple.push_back( data[k] );

            triples.push_back( triple );
        }
    }
}

4倍およびその他のタプルタイプのコードを思い付くのはかなり簡単です。

誰かが、あらゆる種類のタプルを生成するための一般的なアルゴリズムを実現する方法を教えてもらえますか？そして、私たちはそれに取り組んでいるので、ベクトル内の要素の数を指定してタプルの数をどのように計算できますか？ペアの場合、式はn（n-1）/2です。

ありがとう！

4

1 に答える 1

2

あなたが説明しているのはk-combinationsと呼ばれ、組み合わせ論の分野で非常に重要な概念です。n個の要素のセットからのk個の要素の一意の組み合わせの数は、式n！で表されます。/（k！（nk）！）。

std::tupleこれを一般的な方法で効率的に解決するには、おそらく可変個引数テンプレート（C ++ 11機能）を調べる必要があります。ただし、コンパイル時に次元がわからない場合は、すべてのアイテムのリストと、リストから選択するアイテムの数であるkの2つの引数をとる再​​帰関数を作成する必要があります。

次に、セット内の要素eごとに、その要素を含むリストを作成し、k-1を数値として関数を再帰的に呼び出して、リスト内のeの後に続くリストの要素のみを選択して提供します。これにより、再帰の複数のサブツリーに同じサブセットが作成されるのを防ぐことができます。

それがあなたにとって十分に明確であることを願っています。:)他にご不明な点がございましたら、お気軽に説明をお寄せください。

于 2013-01-26T22:36:04.943 に答える