0

私がしなければならないことは、a、 bからの数字の異なる組み合わせの数を形成する必要があることです。たとえば、

n=4 で、a,b が続くとします。

1 2
3 1
2 4
3 2

a、bを見ると合計4つの異なる数があり、それらは（1、2、3、4）です

そして、すべての異なる数の2つの組み合わせを形成することができます.それらは次のように(1,3,4,2)と(2,1,4,3)です:-

 1 2
 | 
 3 1
  \
 2 4
   |
 3 2

と

 1 2
   | 
 3 1
   |
 2 4
  /
 3 2

私の問題は、n<=50 および a,b<=16 のように、コーディング方法を考えることができないことです。そのため、16 個の数字がある場合、可能なすべての数字を見つけなければなりません。 16個の数字の組み合わせなので、これを案内してください.

4

2 に答える 2

2

個別の番号のリストを作成するには、「一意のセット」を使用して、すべての番号を挿入し続けます。C++ では、定義により std::set は一意の数値のみを格納します。

異なるシーケンスの組み合わせの数を見つけるには、「候補リスト」のリストを保持し、それらの番号がまだない場合は番号を挿入し続ける必要があります。そうでない場合は、その特定の候補リストを削除します。

C++ の完全なコード:

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {

    int n = 4;
    set<int> uniqueNumbers; // ordered set of unique numbers
    vector< set<int> > possibleLists( 1 );
    set<int>::iterator it;

    for ( int i = 0; i < n; i++ ) {

        int num1;
        int num2;
        cin >> num1 >> num2;

        // numbers will be inserted if not already present in set (by definition)
        uniqueNumbers.insert( num1 );
        uniqueNumbers.insert( num2 );

        // make a copy for a possible new branch
        vector< set<int> > possibleListsCopy( possibleLists );

        //int size1 = possibleLists.size();

        for ( int j = 0; j < possibleLists.size(); j++ ) {

            it = possibleLists[j].find( num1 );
            if ( it == possibleLists[j].end() ) {
                possibleLists[j].insert( num1 ); // insert if not found
                //cout << "inserted1 "<<endl;
            }
            else {
                // erase this possible combination
                possibleLists[j].clear();
                possibleLists.erase( possibleLists.begin() + j );
                j--;
            }

        }

        //int size2 = possibleListsCopy.size();

        for ( int j = 0; j < possibleListsCopy.size(); j++ ) {
;

            it = possibleListsCopy[j].find( num2 );
            if ( it == possibleListsCopy[j].end() ) {
                possibleListsCopy[j].insert( num2 ); // insert if not found
            }
            else {
                // erase this possible combination
                possibleListsCopy[j].clear();
                possibleListsCopy.erase( possibleListsCopy.begin() + j );
                j--;
            }

        }

        // concatenate both set of lists.
        possibleLists.insert( possibleLists.end(),
                                possibleListsCopy.begin(),
                                possibleListsCopy.end() );


    }


    cout << " The unique list: ";
    //output the unique list.
    for ( it = uniqueNumbers.begin(); it != uniqueNumbers.end(); it++ )
        cout << *it << " ";

    /*cout << endl << endl;

    cout << "Possible Lists:" << endl;

    for ( int i = 0; i < possibleLists.size(); i++ ) {

        for ( it = possibleLists[i].begin(); it != possibleLists[i].end(); it++ )
            cout << *it << " ";
        cout << endl;

    }*/

    cout << endl << "Total number of combinations: "
        << possibleLists.size() << endl;

    return 0;
}

入力: 1 2 3 1 2 4 3 2

出力: 一意のリスト: 1 2 3 4 組み合わせの総数: 2

于 2013-09-12T17:11:27.790 に答える
0

このような組み合わせ問題を解決する場合、再帰はおそらく最も簡単な方法です。現在のアイテムのすべての可能性を考慮してから、残りのアイテムを再帰することで残りの作業を渡すという考え方です。この場合、使用しないアイテムに関する追加情報を少し渡す必要があります。

次のように機能します。

def DistinctChooseFromEach(listOfChoicePairs, alreadyUsed = {}):
    if listOfChoicePairs is empty: return []
    for value in listOfChoicePairs[0]:
        if value in alreadyUsed: continue;
        newUsed = union(alreadyUsed, value)
        remainingChoices = listOfChoicePairs[1:];
        tails = DistinctChooseFromEach(remainingChoices, newUsed)
        for tail in tails:
           yield concat(value, tail)
于 2013-09-12T18:45:21.667 に答える