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}
}
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.
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
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)
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
