Words combinations without repetition

问题:

I have 10 words. How can I get all possible combinations of 5 words (n=10, k=5). The order does not matter.

For example: "A", "B", "C", if k=2 (n=3 in this case), it would like AB, BC and AC. Maybe you know some usefull code or example.

P.S. Sorry if I'm not right enough cause I don't know English very good.

回答1:

What you are trying to do is get all the permutations of a collection.

• Unique permutations of list
• permutations of k objects from a set of n algorithm

Here is the code snippet:

static void Main(string[] args)
{
    var list = new List<string> { "a", "b", "c", "d", "e" };
    var result = GetPermutations(list, 3);
    foreach (var perm in result)
    {
        foreach (var c in perm)
        {
            Console.Write(c + " ");
        }
        Console.WriteLine();
    }
    Console.ReadKey();
}

static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count)
{
    int i = 0;
    foreach (var item in items)
    {
        if (count == 1)
            yield return new T[] { item };
        else
        {
            foreach (var result in GetPermutations(items.Skip(i + 1), count - 1))
                yield return new T[] { item }.Concat(result);
        }

        ++i;
    }
}

Outputs:

a b c 
a b d 
a b e 
a c d 
a c e 
a d e 
b c d 
b c e 
b d e 
c d e 

回答2:

Here's what I put together:

static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> CombinationsWithoutRepetition<T>(
        this IEnumerable<T> items,
        int ofLength)
    {
        return (ofLength == 1) ?
            items.Select(item => new[] { item }) :
            items.SelectMany((item, i) => items.Skip(i + 1)
                                               .CombinationsWithoutRepetition(ofLength - 1)
                                               .Select(result => new T[] { item }.Concat(result)));
    }

    public static IEnumerable<IEnumerable<T>> CombinationsWithoutRepetition<T>(
        this IEnumerable<T> items,
        int ofLength,
        int upToLength)
    {
        return Enumerable.Range(ofLength, Math.Max(0, upToLength - ofLength + 1))
                         .SelectMany(len => items.CombinationsWithoutRepetition(ofLength: len));
    }

}

...

foreach (var c in new[] {"a","b","c","d"}.CombinationsWithoutRepetition(ofLength: 2, upToLength: 4))
{
    Console.WriteLine(string.Join(',', c));
}

produces:

a,b
a,c
a,d
b,c
b,d
c,d
a,b,c
a,b,d
a,c,d
b,c,d
a,b,c,d

Note that this is concise but inefficient and should not be used for large sets or inner loops. Notably, the short arrays are re-created multiple times and could be memoized, and the IEnumerable will be iterated multiple times, which can cause unexpected work if care is not taken.

Also, if the input contains duplicates then the output will as well. Either use .Distinct().ToArray() first, or use another solution which includes equality checking and, presumably, takes an IEqualityComparer for generality.

回答3:

What about a more functional solution

var list = new List<string> { "a", "b", "c", "d", "e" };
GetAllCombinations(list).OrderBy(_ => _).ToList().ForEach(Console.WriteLine);


static IEnumerable<string> GetAllCombinations(IEnumerable<string> list)
{
    return list.SelectMany(mainItem => list.Where(otherItem => !otherItem.Equals(mainItem))
                              .Select(otherItem => mainItem + otherItem));
}

Ouput:

ab
ac
ad
ae
ba
bc
bd
be
ca
cb
cd
ce
da
db
dc
de
ea
eb
ec
ed