Last active
January 31, 2019 19:33
-
-
Save Demonslay335/6d2a86ef5011fc78dc68b5da5f6052bd to your computer and use it in GitHub Desktop.
Generate permutations of an array of arrays
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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