combination of n distinct numbers

Question

I have a set of n case in the format a b what I have to do is I have to form number of distinct combination of numbers from a,b. for e.g.,

suppose n=4 and a,b are are follow

1 2
3 1
2 4
3 2

Now total there are 4 distinct number by seeing a,b, they are(1,2,3,4)

and two combination of all distinct numbers can be formed, they are (1,3,4,2) and (2,1,4,3) as follow :-

 1 2
 | 
 3 1
  \
 2 4
   |
 3 2

and

 1 2
   | 
 3 1
   |
 2 4
  /
 3 2

My problem is I am unable to think how to code, as n<=50 and a,b<=16 so I am not sure that how many distinct number can be there, if there are 16 numbers then I have to find all possible combination of 16 numbers, so guide me through this.

Answer 1

To form a list of distinct numbers just use a "unique set" and keep inserting all the numbers to it. In C++, std::set by definition stores only unique numbers.

To find the number of combinations of distinct sequences, you will have to keep a list of "candidate lists" and keep inserting numbers in them if they already don't have those numbers, else delete that particular candidate list.

Full code in 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;
}

Input: 1 2 3 1 2 4 3 2

Output: The unique list: 1 2 3 4 Total number of combinations: 2

Answer 2

Recursion is probably the easiest route when solving combinatorial problems like this one. The idea is that you consider all the possibilities for the current item, then pass off the rest of the work by recursing on the remaining items. In this case you need to pass along a bit of extra information about what items not to use.

It works something like this:

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)