combinations from a list of items

Question

I have a list of collections:
{A B}
{C D E}
{F G}

The number of rows can be arbitrary and also the number of items in a row can be arbitrary.

I need to get this:
{ACF ACG ADF ADG AEF AEG BCF BCG BDF BDG BEF BEG}

Can someone point to some algorithm that can do this or at least the name of the problem - if there is such.

You are looking for the Cartesian product of three sets. Also tensor product is used in some contexts. — Mehrwolf, Sep 04 '12 at 18:40
A solution is [here](http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors). — Mehrwolf, Sep 04 '12 at 18:46

score 0 · Answer 1 · answered Sep 04 '12 at 18:44

0

You can create a recursive function that accepts the original collection of lists and the current index of the list in the collection. It will then iterate through the items in the list and on every item call itself with the increased index.

answered Sep 04 '12 at 18:44

Victor

653
5
9

score 0 · Answer 2 · answered Sep 26 '12 at 17:55

In your example, you said that you only need this:

{ACF ACG ADF ADG AEF AEG BCF BCG BDF BDG BEF BEG}

If you need all of the other combinations as well, then you might be able to use a class that I wrote to handle common functions for working with the binomial coefficient, which is the type of problem that your problem falls under. It performs the following tasks:

Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial.
Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong.
Converts the index in a sorted binomial coefficient table to the corresponding K-indexes.
Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.
The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.
There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

It should not be hard to convert this class to the language of your choice.

score 0 · Answer 3 · answered Sep 26 '12 at 18:01

Actually it's easy:

Here is the solution in C++, if the first set is A, the second is B and the third is C;

cout << "{ ";
for( int i=0; i<a_size; ++i ) {
  for( int j=0; j<b_size; ++j ) {
    for( int k=0; k<c_size; ++k ) {
      cout << A[ i ] << B[ j ] << C[ k ] << " ";
    }
  }
}
cout << " }\n";

combinations from a list of items

3 Answers3