Having an array, say {A, B, C}
I want to create a collections of collections like this
Array Input: {A, B, C}
Output: {A, B, C},
{AB, C},
{A, BC},
{ABC}
Or in case of {A, B, C, D}
Array Input: {A, B, C, D}
Output: {A, B, C, D},
{AB, C, D},
{ABC, D},
{AB, CD},
{ABCD},
{A, BC, D},
{A, BCD},
{A B CD}
I was thinking about making it in C#, but I haven't been able to solve it yet.
Can you code this algorithm?
CodePudding user response:
Yes, in general case you can encode each possible split as 0
or 1
(true
or false
) to have all the combinations:
A B C D
^ ^ ^
0 or 1 ... 0 or 1
For instance:
ABCD - 000 (no splits)
A,BCD - 100 (split, then no splits)
AB,CD - 010 (no split, split, no split)
ABC,D - 001
AB,C,D - 011
A,B,CD - 110
...
A,B,C,D - 111 (all splits)
Code:
private static IEnumerable<List<List<T>>> MySolution<T>(IEnumerable<T> source) {
if (source is null)
throw new ArgumentNullException(nameof(source));
var array = source.ToArray();
if (array.Length <= 0)
yield break;
for (int mask = 0; mask < 1 << (array.Length - 1); mask) {
List<List<T>> result = new List<List<T>>();
result.Add(new List<T>() { array[0] });
for (int index = 0; index < array.Length - 1; index) {
if ((mask & (1 << index)) != 0)
result.Add(new List<T>() { });
result[result.Count - 1].Add(array[index 1]);
}
yield return result;
}
}
Demo:
char[] demo = new char[] { 'A', 'B', 'C', 'D' };
var result = MySolution(demo)
.Select(rec => "{" string.Join(", ", rec
.Select(item => string.Join("", item))) "}");
Console.WriteLine(string.Join(Environment.NewLine, result));
Output:
{ABCD}
{A, BCD}
{AB, CD}
{A, B, CD}
{ABC, D}
{A, BC, D}
{AB, C, D}
{A, B, C, D}
CodePudding user response:
Let me give you an approach you can use:
You have the list:
{ A, B, C, D}
I propose you to replace each comma by a variable, let's call it s_i
("s" standing for "separator"), where i
is some kind of index, so you get:
Input_List = { "As_1Bs_2Cs_3D"}
The separator might be a comma or a concatenation: ", " or "", both being defined in the collection C_SeparatorList
.
You then do following nested for-loop:
foreach (i_1 in C_SeparatorList):
foreach (i_2 in C_SeparatorList):
foreach (i_3 in C_SeparatorList):
Temp = Replace(Input_List, "s_1", i_1); // replace "s_1" by i_1
Temp = Replace(Temp, "s_2", i_2);
Temp = Replace(Temp, "s_3", i_3);
Print(Temp);
next;
next;
next;
You should get the output you're aiming for.
Have fun implementing this :-)