Generating all Possible Combinations

Question

Given 2 arrays Array1 = {a,b,c...n} and Array2 = {10,20,15....x} how can I generate all possible combination as Strings a(i) b(j) c(k) n(p) where

1 <= i <= 10,  1 <= j <= 20 , 1 <= k <= 15,  .... 1 <= p <= x

Such as:

a1 b1 c1 .... n1  
a1 b1 c1..... n2  
......  
......  
a10 b20 c15 nx (last combination)

So in all total number of combination = product of elements of array2 = (10 X 20 X 15 X ..X x)

Similar to a Cartesian product, in which the second array defines the upper limit for each element in first array.

Example with fixed numbers,

    Array x =  [a,b,c]
    Array y =  [3,2,4] 

So we will have 3*2*4 = 24 combinations. Results should be:

    a1 b1 c1  
    a1 b1 c2  
    a1 b1 c3  
    a1 b1 c4  

    a1 b2 c1  
    a1 b2 c2  
    a1 b2 c3  
    a1 b2 c4


    a2 b1 c1  
    a2 b1 c2  
    a2 b1 c3  
    a2 b1 c4  

    a2 b2 c1  
    a2 b2 c2  
    a2 b2 c3  
    a2 b2 c4


    a3 b1 c1  
    a3 b1 c2  
    a3 b1 c3  
    a3 b1 c4  

    a3 b2 c1  
    a3 b2 c2  
    a3 b2 c3  
    a3 b2 c4 (last)

Answer 1

I'm not willing to give you the complete source code. So here's the idea behind.

You can generate the elements the following way:

I assume A=(a1, a2, ..., an) and B=(b1, b2, ..., bn) (so A and B each hold n elements).

Then do it recursively! Write a method that takes an A and a B and does your stuff:

If A and B each contain just one element (called an resp. bn), just iterate from 1 to bn and concatenate an to your iterating variable.

If A and B each contain more then one element, grab the first elements (a1 resp b1), iterate from 1 to bn and do for each iteration step:

• call the method recursively with the subfields of A and B starting at the second element, i.e. A'=(a2, a3, ..., an) resp B'=(b2, b3, ..., bn). For every element generated by the recursive call, concatenate a1, the iterating variable and the generated element from the recursive call.

Here you can find an analouge example of how to generate things in C#, you "just" have to adapt it to your needs.

Answer 2

Fon another solution not linq based you can use:

public class CartesianProduct<T>
    {
        int[] lengths;
        T[][] arrays;
        public CartesianProduct(params  T[][] arrays)
        {
            lengths = arrays.Select(k => k.Length).ToArray();
            if (lengths.Any(l => l == 0))
                throw new ArgumentException("Zero lenght array unhandled.");
            this.arrays = arrays;
        }
        public IEnumerable<T[]> Get()
        {
            int[] walk = new int[arrays.Length];
            int x = 0;
            yield return walk.Select(k => arrays[x++][k]).ToArray();
            while (Next(walk))
            {
                x = 0;
                yield return walk.Select(k => arrays[x++][k]).ToArray();
            }

        }
        private bool Next(int[] walk)
        {
            int whoIncrement = 0;
            while (whoIncrement < walk.Length)
            {
                if (walk[whoIncrement] < lengths[whoIncrement] - 1)
                {
                    walk[whoIncrement]++;
                    return true;
                }
                else
                {
                    walk[whoIncrement] = 0;
                    whoIncrement++;
                }
            }
            return false;
        }
    }

You can find an example on how to use it here.

Answer 3

using System;
using System.Text;

public static string[] GenerateCombinations(string[] Array1, int[] Array2)
{
    if(Array1 == null) throw new ArgumentNullException("Array1");
    if(Array2 == null) throw new ArgumentNullException("Array2");
    if(Array1.Length != Array2.Length)
        throw new ArgumentException("Must be the same size as Array1.", "Array2");

    if(Array1.Length == 0)
        return new string[0];

    int outputSize = 1;
    var current = new int[Array1.Length];
    for(int i = 0; i < current.Length; ++i)
    {
        if(Array2[i] < 1)
            throw new ArgumentException("Contains invalid values.", "Array2");
        if(Array1[i] == null)
            throw new ArgumentException("Contains null values.", "Array1");
        outputSize *= Array2[i];
        current[i] = 1;
    }

    var result = new string[outputSize];
    for(int i = 0; i < outputSize; ++i)
    {
        var sb = new StringBuilder();
        for(int j = 0; j < current.Length; ++j)
        {
            sb.Append(Array1[j]);
            sb.Append(current[j].ToString());
            if(j != current.Length - 1)
                sb.Append(' ');
        }
        result[i] = sb.ToString();
        int incrementIndex = current.Length - 1;
        while(incrementIndex >= 0 && current[incrementIndex] == Array2[incrementIndex])
        {
                current[incrementIndex] = 1;
                --incrementIndex;
        }
        if(incrementIndex >= 0)
            ++current[incrementIndex];
    }
    return result;
}

Answer 4

Fon another solution not linq based, more effective:

static IEnumerable<T[]> CartesianProduct<T>(T[][] arrays) {
    int[] lengths;
    lengths = arrays.Select(a => a.Length).ToArray();
    int Len = arrays.Length;
    int[] inds = new int[Len];
    int Len1 = Len - 1;
    while (inds[0] != lengths[0]) {
        T[] res = new T[Len];
        for (int i = 0; i != Len; i++) {
            res[i] = arrays[i][inds[i]];
        }
        yield return res;
        int j = Len1;
        inds[j]++;
        while (j > 0 && inds[j] == lengths[j]) {
            inds[j--] = 0;
            inds[j]++;
        }
    }
}

Answer 5

Alternative solution:

Step one: read my series of articles on how to generate all strings which match a context sensitive grammar:

http://blogs.msdn.com/b/ericlippert/archive/tags/grammars/

Step two: define a grammar that generates the language you want. For example, you could define the grammar:

S: a A b B c C
A: 1 | 2 | 3
B: 1 | 2
C: 1 | 2 | 3 | 4

Clearly you can easily generate that grammar definition string from your two arrays. Then feed that into the code which generates all strings in a given grammar, and you're done; you'll get all the possibilities. (Not necessesarily in the order you want them in, mind you.)