CODEWITHSUNDEEP
c#stringalgorithm
thomas
thomas

Reputation: 2642

C# Permutations of String

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.

Upvotes: 0

Views: 1234

Answers (3)

Jonathan Wood
Jonathan Wood

Reputation: 67193

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);
    }
}

Upvotes: 0

Xiaoy312
Xiaoy312

Reputation: 14477

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));
}

Upvotes: 0

Chris
Chris

Reputation: 5514

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!

Upvotes: 3

Related Questions