Finding All Combinations (cartesian product) of li

Question

How can I produce all of the combinations of the values in N number of vb list of variable lengths?

Let's say I have N number of vb lists, e.g.

first = {'a', 'b', 'c', 'd'}
second = {'e'}
third =  {'f', 'g', 'h', 'i', 'j'}

(Three list in this example, but its N number of lists for the problem.)

And I want to output all the combinations of their values, to produce a list of lists in the order.

{
{a,e,f}
{a,e,g}
{a,e,h}
{a,e,i}
{a,e,j}
{b,e,f}
{b,e,g}
....
{d,e,j}
}

Answer 1

A simple way to implement with python

import itertools
first = ['a', 'b', 'c', 'd']
second = ['e']
third = ['f', 'g', 'h', 'i', 'j']
for x in itertools.product (first, second, third):
    print x

Answer 2

Here's a fairly simple-minded way of doing in (i.e. no Linq).

Assuming a form with a Button and a ListBox.

Storing everything in Lists for simplicity:

Private listOfLists As New List(Of List(Of String))
'Something to keep track of where we are...
Private permCount As New List(Of Integer)

Second list is just to keep track of progress through the permutations.

Load up the data...

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load

    listOfLists.Add(New List(Of String)({"a", "b", "c", "d"}))
    listOfLists.Add(New List(Of String)({"e"}))
    listOfLists.Add(New List(Of String)({"f", "g", "h", "i", "j"}))

    For i As Integer = 0 To listOfLists.Count - 1
        permCount.Add(0)
    Next

End Sub

And the rest...

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
    EnumeratePermutations()
End Sub

Private Sub EnumeratePermutations()
    'ideally, reset permCount and ListBox1
    Dim blnFinished As Boolean
    Do Until blnFinished
        WritePerm()
        blnFinished = GetNext()
    Loop
End Sub

Private Sub WritePerm()
    Dim strPerm As String = ""
    For i As Integer = 0 To listOfLists.Count - 1
        strPerm += listOfLists(i)(permCount(i))
    Next
    ListBox1.Items.Add(strPerm)
End Sub

Private Function GetNext() As Boolean
    For i As Integer = listOfLists.Count - 1 To 0 Step -1
        'Increment if we can otherwise reset and move to previous list
        If permCount(i) < listOfLists(i).Count - 1 Then
            permCount(i) += 1
            Return False
        Else
            permCount(i) = 0
        End If
    Next
    'If we got here, then we ran out of permutations
    Return True
End Function

Answer 3

Introduction

What you want to do is called: cartesian product

Let's do some naming before going further. I will name your input lists L_i where 1 <= i <= n. I will also name S_i the size of the input list L_i.

We could ask the question: what is the size of the output ?

If there is only one list L_1, there will be S_1 output lists, each one containing exactly one element of L_1.

If there are two lists {L_1, L_2}. For each element of L_1 I can append S_2 different elements of L_2. As there are S_1 elements of L_1 it makes S_1*S_2 different output lists.

We can continue the reasoning to n lists and prove that the number of output lists will be: S_1*...*S_n.

How does that help us ? Because we can now create a mapping between a number i and an output list.

Given i a number 0<=i<S_1*...*S_n, the output list contains:

element of L_1 at index i/(S_2*S_3*...*S_n) MOD S_1
element of L_2 at index i/(    S_3*...*S_n) MOD S_2
...
element of L_n at index i                   MOD S_n

Implementation example

I don't know VB.net so I chose C# which uses the same .net platform. I decided to use a yield return function so that we don't allocate more memory than needed. If you just need to print the outputs it will only consume a single ulong of memory instead of allocating a very big list of output lists.

using System;
using System.Collections.Generic;
using System.Linq;

namespace cartesian_product
{
    class Program
    {
        public static IEnumerable<List<T>> cartesian_product<T>(IEnumerable<List<T>> lists)
        {
            ulong MAX_I = lists.Select(l => (ulong)l.Count)
                               .Aggregate(1ul, (a, b) => a * b);

            for (ulong i = 0; i < MAX_I; ++i)
            {
                var output = new List<T>();

                ulong div = MAX_I;
                ulong index, s_i;
                foreach (var l in lists)
                {
                    s_i    = (ulong)l.Count;
                    div   /= s_i;
                    index  = (i/div)%s_i;
                    output.Add(l[(int)index]);
                }
                yield return output;
            }
        }

        static void Main(string[] args)
        {
            var first = new List<Char> {'a', 'b', 'c', 'd'};
            var second = new List<Char> {'e'};
            var third = new List<Char> {'f', 'g', 'h', 'i', 'j'};

            Console.WriteLine("{");
            foreach (var output in cartesian_product(new[]{first, second, third}))
            {
                Console.WriteLine("{{{0}}}", string.Join(",", output));
            }
            Console.WriteLine("}");
        }
    }
}

The output is:

{
{a,e,f}
{a,e,g}
{a,e,h}
{a,e,i}
{a,e,j}
{b,e,f}
{b,e,g}
{b,e,h}
{b,e,i}
{b,e,j}
{c,e,f}
{c,e,g}
{c,e,h}
{c,e,i}
{c,e,j}
{d,e,f}
{d,e,g}
{d,e,h}
{d,e,i}
{d,e,j}
}

Limitation

One may ask : what if the product of the lists length overflows the variable used to index the outputs ?.

This is a real theoretical problem, but I use a ulong in my code and if the total number of ouput lists overflows this variable there is little chance that you can enumerate the output whatever method you use. (because the theoretical output will contain more than 2^64 lists).

Applications

The OP didn't explain why he needed this algorithm in the first place. So the reader may wonder why is this useful ?. One reason among others may be to generate test cases for regression testing. Let's say you have a legacy function taking as input three variables. You could generate some possible values for each of the parameters and using the cartesian product collect result of the function for each possible set of parameters. After refactoring the legacy code, you could ensure there is no regression by comparing the new code output and the legacy code output.

Answer 4

This is a combination problem, not one of permutations. We want all combinations of 3 elements, one taken from each set. The order is driven by the sets, not the elements. The total number of combinations is the product of the counts of the set. In the example, that would be 4 x 1 x 5 = 20. Since we don't know how many lists there are (call it N). It we knew what N was ahead of time, this would be easy. We could write some nested loops to generate the combinations. Not knowing it is what's makes this tricky. Recursion is probably the most elegant way to solve it.

Private Function AppendCombinations(Combinations As List(Of List(Of String)), Lists As List(Of List(Of String))) As List(Of List(Of String))
    If Combinations Is Nothing Then
        Combinations = New List(Of List(Of String))
        For Each s As String In Lists.First
            Dim newCombo As New List(Of String)
            newCombo.Add(s)
            Combinations.Add(newCombo)
        Next
        Dim newList As New List(Of List(Of String))
        newList.AddRange(Lists)
        newList.RemoveAt(0)
        Return AppendCombinations(Combinations, newList)
    Else
        Dim newCombinations As New List(Of List(Of String))
        For Each combo In Combinations
            For Each s As String In Lists.First
                Dim newCombo As New List(Of String)
                newCombo.AddRange(combo)
                newCombo.Add(s)
                newCombinations.Add(newCombo)
            Next
        Next
        Dim newList As New List(Of List(Of String))
        newList.AddRange(Lists)
        newList.RemoveAt(0)
        If newList.Count > 0 Then
            Return AppendCombinations(newCombinations, newList)
        Else
            Return newCombinations
        End If
    End If
End Function

This function can be called as follows. This example assumes that the lists are members of another list called lists.

    Dim combinations As List(Of List(Of String))
    combinations = AppendCombinations(combinations, lists)