C# Permutations of String

Question

I have strings like 1,2|3,4 and 1|2,3|4 and need to get the following permutations out of them (as an array/list).

Given 1,2|3,4 need to get 2 strings: 1,2,4 1,3,4

Given 1|2,3|4 need to get 4 strings: 1,3 1,4 2,3 2,4

It is basically splitting on the commas and then if those elements have a pipe create permutations for every pipe delimited sub-element (of the remaining elements). The solution needs to handle the general case of an unknown number of elements with pipes.

Interested in any solution that uses standard C# libraries.

Getting stuck on this one so searching for some thoughts from the community. I can't seem to get past the element with pipes...its almost like a "look ahead" is needed or something as I need to complete the string with the remaining comma separated elements (of which some may have pipes, which makes me think recursion but still can't wrap my head around it yet).

Ultimately order does not matter. The comma and pipe delimited elements are numbers (stored a strings) and the final string order does not matter so 1,2,4 = 1,4,2

And no, this is not homework. School ended over a decade ago.

I've done plenty of combinations, permutations, etc implementations.. but I really don't understand what you're trying to do here. If you don't care about order, you want combinations, instead of permutations. — Erti-Chris Eelmaa
– Erti-Chris Eelmaa, Commented Jan 21, 2015 at 17:34
If I am reading it correctly, the pipes indicate or, so in the first example, 1 and (2 or 3) and 4. And in the second case (1 or 2) and (3 or 4) — John Koerner
– John Koerner, Commented Jan 21, 2015 at 17:39
I have a CSV string and some of the elements in that CSV string are themselves pipe delimited. And need to get all permutations of CSV elements combined with pipe delimited elements. — thomas
– thomas, Commented Jan 21, 2015 at 17:39
You could split the string on the pipes first, then on the commas. Finally you could take the cartesian product of the remaining lists and voila, piece of cake. Implementing this via LINQ should be fairly doable. — ThreeFx
– ThreeFx, Commented Jan 21, 2015 at 17:40

Chris · Accepted Answer · 2015-01-21 18:39:10Z

We can do this in a fancy way with LINQ. First, we'll need Eric Lippert's CartesianProduct extension method:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>( this IEnumerable<IEnumerable<T>> sequences ) { IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; return sequences.Aggregate( emptyProduct, ( accumulator, sequence ) => from accseq in accumulator from item in sequence select accseq.Concat( new[] { item } ) ); }

Then we can simply do:

var a = "1|2,3|4".Split( ',' ); var b = a.Select( x => x.Split( '|' ) ); var res = b.CartesianProduct().Select( x => string.Join( ",", x ) );

And we're done!

Xiaoy312 · Accepted Answer · 2015-01-21 18:48:14Z

I couldn't think of any edge cases now, but this works for both of your examples :

public IEnumerable<string> GetPermutation(string pattern) { var sets = pattern.Split(','); var permutations = new[] { new string[] { } }; foreach(var set in sets) { permutations = set.Split('|') .SelectMany(s => permutations.Select(x => x.Concat(new [] { s }).ToArray())) .ToArray(); } return permutations.Select(x => string.Join(",", x)); }

Jonathan Wood · Accepted Answer · 2015-01-21 18:54:24Z

Looks like the LINQ solutions won out, at least as far as conciseness is concerned.

Here's my first attempt at the problem with plain C# code.

protected List<string> Results = new List<string>(); void GetPermutations(string s) { Results = new List<string>(); string[] values = s.Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries); GetPermutationsRecursive(String.Empty, values, 0); } void GetPermutationsRecursive(string soFar, string[] values, int index) { if (index < values.Length) { foreach (var y in GetVariations(values[index])) { string s = String.Format("{0}{1}{2}", soFar, soFar.Length > 0 ? "," : String.Empty, y); GetPermutationsRecursive(s, values, index + 1); } } else { Results.Add(soFar); } } IEnumerable<string> GetVariations(string s) { int pos = s.IndexOf('|'); if (pos < 0) { yield return s; } else { yield return s.Substring(0, pos); yield return s.Substring(pos + 1); } }

Collectives™ on Stack Overflow

C# Permutations of String

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related