Get all the combinations of List<List<int>> (with partial results, too) in C#

I need an efficient algorithm to get all the available combinations of a list of lists of integers. I need the partial results, too.

An example:

{1, 2, 3}
{4, 5}
{6, 7, 8}

I need to get:

1
2
3
1/4
1/5
2/4
2/5
3/4
3/5
1/4/6
1/4/7
1/4/8
1/5/6
1/5/7
1/5/8
开发者_Go百科2/4/6
2/4/7
2/4/8
2/5/6
2/5/7
2/5/8
3/4/6
3/4/7
3/4/8
3/5/6
3/5/7
3/5/8

I need it in the fastest way, if possible. I already have an algorithm, but I want to find out if there are better alternatives.

Thank you.

EDIT: This is my current code. Sorry for the italian comments.

// Istanzia una lista per contenere le liste di valori
List<List<int>> allLists = new List<List<int>>();

... CODE TO FILL THE LISTS ...

// Esegue un ciclo fino al numero di liste recuperate
for (int listIndex = 0; listIndex < allLists.Count; listIndex++)
{
    // Istanzia una lista per contenere le liste di valori fino allo 
    // step corrente
    List<List<int>> stepLists = new List<List<int>>();

    // Esegue un ciclo sulle liste fino allo step corrente
    for (int stepListIndex = 0; stepListIndex <= listIndex; stepListIndex++)
    {
        // Aggiunge la lista a quelle dello step corrente
        stepLists.Add(allLists[stepListIndex]);
    }

    // Esegue il prodotto vettoriale delle liste specificate
    List<List<int>> crossLists = 
        Mathematics.CrossProduct(stepLists, new List<int>());

    // Carica l'elenco delle combinazioni
    CombinationsCollection allCombinations = 
        new CombinationsCollection(Kernel);
    allCombinations.Load();

    // Esegue un ciclo su ciascuna lista recuperata
    foreach (List<int> crossList in crossLists)
    {
    }
}

... OTHER CODE ...

public static List<List<int>> CrossProduct(
    List<List<int>> lists, 
    List<int> root)
{
    // Istanzia delle liste per contenere le combinazioni
    List<List<int>> results = new List<List<int>>();

    // Se ce n'è almeno una
    if (lists.Count > 0)
    {
        // Recupera la prima lista
        List<int> list = (List<int>)lists[0];

        // Se è rimasta solo una lista
        if (lists.Count == 1)
        {
            // Esegue un ciclo su tutti i valori
            foreach (int value in list)
            {
                // Aggiunge un risultato con radice e valore
                results.Add(new List<int>(root) { value });
            }
        }
        else
        {
            // Esegue un ciclo su ogni valore della lista
            foreach (int value in list)
            {
                // Aggiunge ai risultati la prosecuzione del prodotto 
                // vettoriale dalla lista successiva
                results.AddRange(CrossProduct(
                    lists.GetRange(1, lists.Count - 1), 
                    new List<int>(root) { value })
                );
            }
        }
    }

    return results;
}

You need a method which returns a cartesian product of your lists plus partial results (as you mentioned in title). Here is a variance of CartesianProduct method extension from Eric Lippert with partial results as per your request:

public static IEnumerable<IEnumerable<T>> CrossProduct<T>(
     this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> accumulator = new[] { Enumerable.Empty<T>() };
    var result = new List<IEnumerable<T>>();
    var firstSequence = true;
    foreach (var sequence in sequences)
    {
        var local = new List<IEnumerable<T>>();
        foreach (var accseq in accumulator)
        {
            if (!firstSequence)
                result.Add(accseq);

            foreach (var item in sequence)
                local.Add(accseq.Concat(new[] { item }));
        }
        firstSequence = false;
        accumulator = local;
    }

    return result.Concat(accumulator);
}

For the input data you provided:

var items = new[] { 
    new[] { 1, 2, 3 }, 
    new[] { 4, 5 }, 
    new[] { 7, 8, 9 } 
};
var product = items.CrossProduct();

the product variable will contain the result you want.

I believe what you are looking for is the cartesian product of each element of the power set "prefix set" of your set of sequences. Let's break it down:

First, you have a set of input sequences:

IEnumerable<IEnumerable<int>> inputSet = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};

The "prefix set" of inputSet is:

{ {}, {1,2,3}, { {1,2,3},{4,5} }, { {1,2,3},{4,5},{6,7,8} } }

The cartesian product of a set of sequences yields all combinations of 1 item from each sequence.

What I believe you are looking for is: (pseudocode)

foreach (element in the above prefix set)
{
  Print(cartesian product of the sequences in this element);
}

The following are extension methods I use to generate cartesian products, power sets, etc.:

public static class CombinatorialExtensionMethods {
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
    { 
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence  
            select accseq.Concat(new[] {item}));                
    }

    public static IEnumerable<IEnumerable<T>> CartesianPower<T>(this IEnumerable<T> sequence, int power) 
    { 
        var sequences = Enumerable.Repeat<IEnumerable<T>>(sequence,power);
        return sequences.CartesianProduct<T>();
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> seq, int k)
    { 
        var sequences = Enumerable.Repeat<IEnumerable<T>>(seq,k);
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where !accseq.Contains(item)
            select accseq.Concat(new[] {item}));
    }

    public static IEnumerable<IEnumerable<int>> Choose(this IEnumerable<int> seq, int k)
    { 
        var sequences = Enumerable.Repeat<IEnumerable<int>>(seq,k);
        IEnumerable<IEnumerable<int>> emptyProduct = new[] { Enumerable.Empty<int>() }; 
        return sequences.Aggregate( 
            emptyProduct, 
            (accumulator, sequence) =>  
            from accseq in accumulator  
            from item in sequence
            where accseq.All(accitem => accitem.CompareTo(item) < 0)
            select accseq.Concat(new[] {item}));
    }

    public static IEnumerable<IEnumerable<T>> Choose<T>(this IEnumerable<T> seq, int k)
    { 
        IEnumerable<int> idxSequence = Enumerable.Range(0, seq.Count());
        IEnumerable<IEnumerable<int>> idxChoose = idxSequence.Choose(k);
        IEnumerable<IEnumerable<T>> result = Enumerable.Empty<IEnumerable<T>>(); 
        foreach (IEnumerable<int> permutation in idxChoose)
        {
            IEnumerable<T> item = Enumerable.Empty<T>();
            foreach (int index in permutation)
            {
                item = item.Concat(new[] { seq.ElementAt(index) });
            }
            result = result.Concat(new[] { item });
        }
        return result;
    }

    public static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> seq)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
        for (int i=1; i<=seq.Count(); i++)
        {
            result = result.Concat(seq.Choose<T>(i));
        }

        return result;
    }
}

Using these, the code for your example would be:

IEnumerable<IEnumerable<int>> sequences = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};
IEnumerable<IEnumerable<IEnumerable<int>>> prefixSet = new[] {new[] { Enumerable.Empty<int>() }};

for (int i=0; i<sequences.Count(); i++)
{
    IEnumerable<IEnumerable<int>> prefixSequence = Enumerable.Empty<IEnumerable<int>>();
    for (int j=0; j<=i; j++)
    {
        prefixSequence = prefixSequence.Concat(new[] { sequences.ElementAt(j) });
    }
    prefixSet = prefixSet.Concat(new[] { prefixSequence });
}

foreach (IEnumerable<IEnumerable<int>> item in prefixSet)
{
    Console.WriteLine(item.CartesianProduct<int>());
}

This will produce the desired output. Not sure about performance compared to the original coding though:

private List<List<int>> test(List<List<int>> lists)
{
    List<List<int>> ret = new List<List<int>>();
    ret.AddRange(from first in lists[0] select new List<int>(new int[] { first }));

    List<List<int>> inner = new List<List<int>>();
    inner.AddRange(from first in lists[0] select new List<int>(new int[] { first }));

    for (int i = 1; i < lists.Count;i++ )
    {
        List<int> l = lists[i];

        var newElements =
          from first in inner
          from second in l
          select new List<int>(first.Concat<int>(new int[] { second }));

        ret.AddRange(newElements);
        inner = newElements.ToList();
    }

    return ret;
}

If called using

        List<List<int>> rval = test(
            new List<List<int>>(
                new List<int>[] { 
                    new List<int>(new int[] { 1, 2, 3 }),
                    new List<int>(new int[] { 4, 5 }),
                    new List<int>(new int[] { 6, 7, 8 })
            }));

the resulting rval contains the elements in the way required.

Probably some of the Linq stuff in there can be refactored to something easier or more performant, I'm not on solid ground with this stuff (which is why I tested it before I posted it ;-))