Expanding wildcards in a csv string to generate a collection of csv strings?

I'd like create a collection of strings (using C# and possibly LINQ) from a single csv string where each value is a plus or minus sign followed by a character. For example:

"+A,+E,+B,-B,+C,+D"

Th开发者_运维问答e string could also contain a wild card representing two of any character; one with a plus sign and then one with a negative sign. If a string does contain a wild card I'd like substitute out the wild card and generate a list of strings without wild cards. For example say I had:

"+A,-A,*"

The strings I'd want to generate would be:

+A,-A,+A,-A
+A,-A,+B,-B
+A,-A,+C,-C
+A,-A,...
+A,-A,+Z,-Z

And likewise for multiple wildcards. The string "*,*" would produce:

+A,-A,+A,-A
+A,-A,+B,-B
+A,-A,+C,-C
+A,-A,...
+A,-A,+Z,-Z
+B,-B,+A,-A
+B,-B,+B,-B
+B,-B,+C,-C
+B,-B,...
+B,-B,+Z,-Z
+C,-C,...

My gut tells me there must be a simple elegant solution, but it's eluding me today. Any ideas? This seems a like a perfect algorithm to take advantage of LINQ with? Thanks your help!

IEnumerable<string> Wildcard = from c in Enumerable.Range(0, 26)
                               let ch = (char)('A' + c)
                               select string.Concat('+', ch, ',', '-', ch);

IEnumerable<string> ExpandLine(string[] xs, int i)
{
    var ys = (xs[i] == "*") ? Wildcard : new[] { xs[i] };

    if (i == xs.Length - 1)
        return ys;
    else
        return from y in ys
               from z in ExpandLine(xs, i + 1)
               select y + "," + z;
}

IEnumerable<string> ExpandLines(IEnumerable<string> xs)
{
    return from x in xs
           from y in ExpandLine(x.Split(','), 0)
           select y;
}

Example:

var result = ExpandLines(new[] { "+A,-A,*" }).ToList();

Result:

+A,-A,+A,-A
+A,-A,+B,-B
+A,-A,+C,-C
     :
     :
+A,-A,+Z,-Z

(26 items)

Example 2:

var result = ExpandLines(new[] { "+A,-A,*,*" }).ToList();

Result:

+A,-A,+A,-A,+A,-A
+A,-A,+A,-A,+B,-B
+A,-A,+A,-A,+C,-C
        :
        :
+A,-A,+Z,-Z,+X,-X
+A,-A,+Z,-Z,+Y,-Y
+A,-A,+Z,-Z,+Z,-Z

(676 items)

A generalization of your problem is the production of every string that conforms to a particular context free grammar. I've written a nine-part series on how to do such a thing in C#; it might be of interest to you if you have more complex problems in this vein.

http://blogs.msdn.com/b/ericlippert/archive/tags/grammars/

Here's another one:

IEnumerable<string> ExpandWildcards(IEnumerable<string> lines)
{
    return lines.SelectMany(ExpandWildcards);
}

IEnumerable<string> ExpandWildcards(string input)
{
    string[] parts = input.Split(',');
    var expanded = parts.Select(ExpandSingleItem);
    return expanded.CartesianProduct().Select(line => line.JoinStrings(","));
}

static readonly string _chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

IEnumerable<string> ExpandSingleItem(string item)
{
    if (item == "*")
        return _chars.Select(c => string.Format("+{0},-{0}", c));
    return new[] { item };
}

static class Extensions
{
    // CartesianProduct method by Eric Lippert (http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/)
    public 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}));                
    }

    public static string JoinStrings(this IEnumerable<string> strings, string separator)
    {
        return strings.Aggregate(
                        default(StringBuilder),
                        (sb, item) => sb == null
                            ? new StringBuilder(item)
                            : sb.Append(separator).Append(item),
                        sb => sb.ToString());
    }
}

Admittedly, it's a bit longer than dtb's solution... But it isn't recursive, which can be important if you have many items per line. It gives the same results.