Recursive algorithm to generate all combinations of elements in successive enumerables

If you need to flatten ordered enumerables, that is taking one element of each enumerable, in order, to flatten a combination, here is a quick solution in C# and VB.NET, accompanied with an example:

Code in VB.NET:

Private Shared Sub GetCombinationsRec(Of T)(sources As IList(Of IEnumerable(Of T)), chain As T(), index As Integer, combinations As ICollection(Of T()))
	For Each element As var In sources(index)
		chain(index) = element
		If index Is sources.Count - 1 Then
			Dim finalChain = New T(chain.Length - 1) {}
			chain.CopyTo(finalChain, 0)
			combinations.Add(finalChain)
		Else
			GetCombinationsRec(sources := sources, chain := chain, index := index + 1, combinations := combinations)
		End If
	Next
End Sub

Public Shared Function GetCombinations(Of T)(ParamArray enumerables As IEnumerable(Of T)()) As List(Of T())
	Dim combinations = New List(Of T())(enumerables.Length)
	If enumerables.Length > 0 Then
		Dim chain = New T(enumerables.Length - 1) {}
		GetCombinationsRec(sources := enumerables, chain := chain, index := 0, combinations := combinations)
	End If
	Return combinations
End Function

Code in C#.NET:

private static void GetCombinationsRec<T>(IList<IEnumerable<T>> sources, T[] chain, int index, ICollection<T[]> combinations) {
	foreach (var element in sources[index]) {
		chain[index] = element;
		if (index == sources.Count - 1) {
			var finalChain = new T[chain.Length];
			chain.CopyTo(finalChain, 0);
			combinations.Add(finalChain);
		}
		else {
			GetCombinationsRec(sources: sources, chain: chain, index: index + 1, combinations: combinations);
		}
	}
}

public static List<T[]> GetCombinations<T>(params IEnumerable<T>[] enumerables) {
	var combinations = new List<T[]>(enumerables.Length);
	if (enumerables.Length > 0) {
		var chain = new T[enumerables.Length];
		GetCombinationsRec(sources: enumerables, chain: chain, index: 0, combinations: combinations);
	}
	return combinations;
}

Usage is simple:

Dim list1 = New String() {"hello", "bonjour", "hallo", "hola"}
Dim list2 = New String() {"Erwin", "Larry", "Bill", "Steve"}
Dim list3 = New String() {"!", ".."}
Dim result = Utils.GetCombinations(list1, list2, list3)
For Each r In result
    Debug.Print(String.Join(" "c, r))
Next

or in C#:

var list1 = new[] { "Hello", "Bonjour", "Hallo", "Hola" };
var list2 = new[] { "Erwin", "Larry", "Bill", "Steve" };
var list3 = new[] { "!", "..." };
var result = Utils.GetCombinations(list1, list2, list3);
foreach (r in result) {
    Debug.Print(string.Join(" ", r));
}

As with any recursive function, memory usage can be exponential so make sure you know the number of target combinations is reasonable. Speed-wise, parallelizing this function is not worth it as we are just iterating over the elements.

2 comments for post “Recursive algorithm to generate all combinations of elements in successive enumerables”

  1. robopro
    3 June 2012 | 10:40 PM

    I was unable to get the vb code to wrk
    something about

    Dim result = Utils.GetCombinations(list1, list2, list3)

    It would error out here telling me to generate a stub please help

  2. 4 June 2012 | 04:15 AM

    You have to declare the function as part of a public class named MyLib:

    Public Class Utils
    Public Shared Function GetCombinations(…)
    End Function
    End Class

Leave a comment