finding possible combinations linq

问题:

I need to generate all possible combinations between {"a", "b","c"}.

For example, an input set say like {"a", "b","c"}, expected output is {"a", "b", "c" "ab", "ac", "bc", "abc"}.

回答1:

It sounds like what you're looking for is basically a form of power set. Here's a simple implementation (taken from this site):

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(this IList<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

Note that thanks to the << operator, you won't be able to use this method with lists that have more than 30 elements. I wouldn't recommend trying it with a list with close to that many elements anyway, since at 30 elements, the result set would contain 2³⁰ or 1073741824 elements.

You can use this method to get the result you want like this

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet()
           select string.Concat(s);
}

However, because the power set includes the null set, this will actually return the result {"", "a", "b", "c", "ab", "ac", "bc", "abc"}. To filter out the empty string, use this:

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet()
           let str = string.Concat(s)
           where str.Length > 0 // exclude null set result
           select str;
}

Or more simply:

public IEnumerable<string> GetPermutations(IList<string> strings)
{
    return from s in strings.GetPowerSet().Skip(1)
           select string.Concat(s);
}