This is a difficult one to describe in terms of using the correct terminology for exactly what problem I was solving when I came up with this code. I think the following example is the best way to convey what problem this solution is designed to solve.
Imagine you have a sort of 2-dimensional jagged array (in my case a list of lists) where the x dimension represents the passing of time and the y dimension represents the various options/forks in the data which could be used in that segment.
e.g.
| 0 | 1 | 2 |
| A | A | A |
| | B | B |
| | C | |
In the above, segment 0 of time can only use option "A", segment 1 can use "A", "B" or "C", segment 2 can use "A" or "B".
Given this above set of data, there are a finite number of possible combinations the data can be used (which is equal to the multiple aggregate value of the counts of the y values) i.e.:
1 * 3 * 2 = 6 combinations
And I wanted a way to have a single pass at the data and build the truth table of possible permutations by filling in the gaps left by lack of any option e.g.:
| 0 | 1 | 2 |
| A | A | A |
| A | A | B |
| A | B | A |
| A | B | B |
| A | C | A |
| A | C | B |
My idea was that, ahead of time for a given permutation, you know how many times the input options of each segment should be repeated into the output matrix in order to end up with all the permutations. At the same time, you must occasionally reverse the output order in order not generate a mirror image of an existing permutation.
The code I came up with, an example of which can be seen below, can be used with any combination of x and y counts and returns the value containing all distinct permutations:
private static List<string>[] GetFullCombinations(List<List<string>> segmentOptions)
{
var totalPermutations = segmentOptions.Aggregate(1, (x, y) => x * y.Count);
var combos = new List<string>[totalPermutations];
var repetitions = totalPermutations;
foreach (var options in segmentOptions)
{
repetitions /= options.Count;
var optionIndex = 0;
for (var permutation = 0; permutation < totalPermutations; permutation++)
{
if ((permutation + 1) % repetitions == 0)
optionIndex = (optionIndex + 1) % options.Count;
var option = options[optionIndex];
if (combos[permutation] == null)
{
combos[permutation] = new List<string>(segmentOptions.Count);
}
combos[permutation].Add(option);
}
}
return combos;
}
Due to the "no mirror images" modular arithmetic, the output is actually in a slightly different order to how a human might have ordered it (in my first table), nevertheless all combinations are returned:
[Test]
public void GetFullCombinations_WhenInputSegmentsHaveOptions_ReturnsAllDistinctPermutations()
{
var input = new List<List<string>>
{
new List<string>
{
"A"
},
new List<string>
{
"A",
"B",
"C"
},
new List<string>
{
"A",
"B"
}
};
var expectedPermutations = new[]
{
new [] { "A", "A", "A" },
new [] { "A", "A", "B"},
new [] { "A", "B", "A"},
new [] { "A", "B", "B"},
new [] { "A", "C", "A"},
new [] { "A", "C", "B"}
};
var result = GetFullCombinations(input);
using (new AssertionScope())
{
foreach (var expectedPermutation in expectedPermutations)
{
result.Should().ContainEquivalentOf(expectedPermutation, cfg => cfg.WithStrictOrdering());
}
}
}
