Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Generate permutations of an array of arrays
// Get permutations of an array of arrays
// Adapted from: https://www.geeksforgeeks.org/combinations-from-n-arrays-picking-one-element-from-each-array/
public static IEnumerable<List<T>> PermutationsOfArrays<T>(IList<List<T>> arr)
{
// Number of arrays
int n = arr.Count();
// Keep track of next element in each of the n arrays
int[] indices = new int[n];
List<List<T>> results = new List<List<T>>();
while (true)
{
// Build current combination
List<T> result = new List<T>();
for (int i = 0; i < n; i++)
{
result.Add(arr[i][indices[i]]);
}
// Yield the result
yield return result;
// Find the rightmost array that has more elements left after the current element in that array
int next = n - 1;
while (next >= 0 && (indices[next] + 1 >= arr[next].Count))
{
next--;
}
// No such array is found so no more combinations left
if (next < 0)
{
yield break;
}
// If found move to next element in that array
indices[next]++;
// For all arrays to the right of this array current index again points to first element
for (int i = next + 1; i < n; i++)
{
indices[i] = 0;
}
}
}
// Helper for outputting nested list
public static void OutputNestedList<T>(IEnumerable<IEnumerable<T>> list)
{
foreach(var li in list)
{
Console.WriteLine("{" + string.Join(", ", li) + "}");
}
}
// Example use
public void Main()
{
List<List<int>> integers = new List<List<int>>(){
new List<int>(){1, 2, 3},
new List<int>(){4},
new List<int>(){5, 6, 7}
};
Console.WriteLine("Integers: ");
OutputNestedList(integers);
Console.WriteLine("");
IEnumerable<IEnumerable<int>> permutations = PermutationsOfArrays(integers);
Console.WriteLine("Permutations: ");
OutputNestedList(permutations);
/*
Integers:
{1, 2, 3}
{4}
{5, 6, 7}
Permutations:
{1, 4, 5}
{1, 4, 6}
{1, 4, 7}
{2, 4, 5}
{2, 4, 6}
{2, 4, 7}
{3, 4, 5}
{3, 4, 6}
{3, 4, 7}
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.