Split and merge several logical "branches" of string data

Question

I know there are a couple of similarly formulated questions about SO about permutations of listings, but they don't seem to address exactly what I'm looking for. I know there is a way to do this, but I draw a space. I have a flat file similar to this format:

Col1|Col2|Col3|Col4|Col5|Col6 a|b,c,d|e|f|g,h|i . . . 

Now here's the trick: I want to create a list of all possible permutations of these lines, where the list, separated by commas in the line, represents possible values. For example, I would have to take the IEnumerable<string> representing above into the strings as such:

 IEnumerable<string> row = new string[] { "a", "b,c,d", "e", "f", "g,h", "i" }; IEnumerable<string> permutations = GetPermutations(row, delimiter: "/"); 

This should generate the following collection of string data:

 a/b/e/f/g/i a/b/e/f/h/i a/c/e/f/g/i a/c/e/f/h/i a/d/e/f/g/i a/d/e/f/h/i 

It seems to me that it will fit elegantly into the recursive method, but apparently I have a bad case of Monday, and I can’t completely plug my brain around how to approach it. Some help would be greatly appreciated. What should GetPermutations(IEnumerable<string>, string) look like?

Answer 1

I really thought it would be a great recursive function, but I didn't write like that. Ultimately, this is the code I created:

 public IEnumerable<string> GetPermutations(IEnumerable<string> possibleCombos, string delimiter) { var permutations = new Dictionary<int, List<string>>(); var comboArray = possibleCombos.ToArray(); var splitCharArr = new char[] { ',' }; permutations[0] = new List<string>(); permutations[0].AddRange( possibleCombos .First() .Split(splitCharArr) .Where(x => !string.IsNullOrEmpty(x.Trim())) .Select(x => x.Trim())); for (int i = 1; i < comboArray.Length; i++) { permutations[i] = new List<string>(); foreach (var permutation in permutations[i - 1]) { permutations[i].AddRange( comboArray[i].Split(splitCharArr) .Where(x => !string.IsNullOrEmpty(x.Trim())) .Select(x => string.Format("{0}{1}{2}", permutation, delimiter, x.Trim())) ); } } return permutations[permutations.Keys.Max()]; } 

... my testing conditions provided me with exactly what I expected:

 IEnumerable<string> row = new string[] { "a", "b,c,d", "e", "f", "g,h", "i" }; IEnumerable<string> permutations = GetPermutations(row, delimiter: "/"); foreach(var permutation in permutations) { Debug.Print(permutation); } 

This produced the following conclusion:

 a/b/e/f/g/i a/b/e/f/h/i a/c/e/f/g/i a/c/e/f/h/i a/d/e/f/g/i a/d/e/f/h/i 

Thanks to all the suggestions, they really helped to figure out what needed to be done in my mind. I supported all your answers.

Answer 2

I'm not sure this is the most elegant approach, but you can start.

 private static IEnumerable<string> GetPermutations(IEnumerable<string> row, string delimiter = "|") { var separator = new[] { ',' }; var permutations = new List<string>(); foreach (var cell in row) { var parts = cell.Split(separator); var perms = permutations.ToArray(); permutations.Clear(); foreach (var part in parts) { if (perms.Length == 0) { permutations.Add(part); continue; } foreach (var perm in perms) { permutations.Add(string.Concat(perm, delimiter, part)); } } } return permutations; } 

Of course, if the order of permutations is important, you can add .OrderBy() to the end.

Edit: added alternate

You can also create a list of string arrays by calculating some numbers before defining permutations.

 private static IEnumerable<string> GetPermutations(IEnumerable<string> row, string delimiter = "|") { var permutationGroups = row.Select(o => o.Split(new[] { ',' })).ToArray(); var numberOfGroups = permutationGroups.Length; var numberOfPermutations = permutationGroups.Aggregate(1, (current, pg) => current * pg.Length); var permutations = new List<string[]>(numberOfPermutations); for (var n = 0; n < numberOfPermutations; n++) { permutations.Add(new string[numberOfGroups]); } for (var position = 0; position < numberOfGroups; position++) { var permutationGroup = permutationGroups[position]; var numberOfCharacters = permutationGroup.Length; var numberOfIterations = numberOfPermutations / numberOfCharacters; for (var c = 0; c < numberOfCharacters; c++) { var character = permutationGroup[c]; for (var i = 0; i < numberOfIterations; i++) { var index = c + (i * numberOfCharacters); permutations[index][position] = character; } } } return permutations.Select(p => string.Join(delimiter, p)); } 

Answer 3

You're me on the "recursive". Here is another suggestion:

 private IEnumerable<string> GetPermutations(string[] row, string delimiter, int colIndex = 0, string[] currentPerm = null) { //First-time initialization: if (currentPerm == null) { currentPerm = new string[row.Length]; } var values = row[colIndex].Split(','); foreach (var val in values) { //Update the current permutation with this column next possible value.. currentPerm[colIndex] = val; //..and find values for the remaining columns.. if (colIndex < (row.Length - 1)) { foreach (var perm in GetPermutations(row, delimiter, colIndex + 1, currentPerm)) { yield return perm; } } //..unless we've reached the last column, in which case we create a complete string: else { yield return string.Join(delimiter, currentPerm); } } } 

Answer 4

One algorithm you can use is mostly similar to counting:

• Start with the 0th item in each list (00000)
• Add the last value (00001, 00002, etc.).
• If you cannot increase one value, reset and increase the next (00009, 00010, 00011, etc.)
• When you cannot increase any value, everything will be ready.

Functions:

 static IEnumerable<string> Permutations( string input, char separator1, char separator2, string delimiter) { var enumerators = input.Split(separator1) .Select(s => s.Split(separator2).GetEnumerator()).ToArray(); if (!enumerators.All(e => e.MoveNext())) yield break; while (true) { yield return String.Join(delimiter, enumerators.Select(e => e.Current)); if (enumerators.Reverse().All(e => { bool finished = !e.MoveNext(); if (finished) { e.Reset(); e.MoveNext(); } return finished; })) yield break; } } 

Using:

 foreach (var perm in Permutations("a|b,c,d|e|f|g,h|i", '|', ',', "/")) { Console.WriteLine(perm); }