CODEWITHSUNDEEP
c#stringcombinations
Frankie Drake
Frankie Drake

Reputation: 1388

How can I create all possible combinations for a set of words 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", with k=2 and n=3 should result in "AB", "BC" and "AC".

Upvotes: 9

Views: 19392

Answers (4)

小小皮
小小皮

Reputation: 11

public IActionResult Index() 
{
    var list = new List<string> { "a", "b", "c", "d", "e" };
    List<string> ret = GetAllCombinations(list).OrderBy(_ => _).ToList();

    return View();
}

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

Ouput ret:

ab
ac
ad
ae
bc
bd
be
cd
ce
de

Upvotes: 1

Tim Sylvester
Tim Sylvester

Reputation: 23168

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.

Upvotes: 2

Jhonattan
Jhonattan

Reputation: 492

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

Upvotes: 0

jrbeverly
jrbeverly

Reputation: 1621

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

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

Upvotes: 26

Related Questions