-
Notifications
You must be signed in to change notification settings - Fork 1
/
Program.java
71 lines (63 loc) · 2.11 KB
/
Program.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Program
{
static void Main(string[] args)
{
int N = 3;
var A = new string[N][];
A[0] = new string[]{"a", "b", "c"};
A[1] = new string[]{"d", "e", "f"};
A[2] = new string[]{"1", "2", "3"};
/* We first need to get all possible combinations of the N arrays.
To do this we consider all integers from 1 to 2 ^ N - 1 expressed
in binary. The positions of the 1's in these binary strings will tell
us whether to include a particular array in a given combination or not.
We order these by the number of 1's in each binary string and then
reverse the strings so that the results will be presented in the required order.
*/
int max = (int)Math.Pow(2, N) - 1;
string[] B = Enumerable.Range(1, max).
Select(i -> Convert.ToString(i, 2).PadLeft(N, '0')).
OrderBy(s -> s.ToCharArray().Count(c -> c == '1')).
Select(s -> new string(s.Reverse().ToArray())).
ToArray();
/* Now get all the combinations by choosing one element from each array specfied
in each binary string using recursion.
*/
List<string> C = GetCombinations(A, B);
Console.WriteLine(String.Join(",", C));
Console.ReadKey();
}
static List<string> GetCombinations(string[][] A, string[] B)
{
var C = new List<string>();
var sb = new StringBuilder();
for(int x = 0; x < B.Length; x++)
{
GetNextLevel(A, B, x, 0, sb, C);
}
return C;
}
static void GetNextLevel(string[][] A, string[] B, int x, int y, StringBuilder sb, List<string> C)
{
if (y < A.Length)
{
if (B[x][y] == '1')
{
foreach(string t in A[y])
{
sb.Append(t);
GetNextLevel(A, B, x, y + 1, sb, C);
sb.Length = sb.Length - 1;
}
}
else
{
GetNextLevel(A, B, x, y + 1, sb, C);
}
}
else
{
C.Add(sb.ToString());
}
}
}