Словосочетания без повторения - PullRequest
Новая
       21

Словосочетания без повторения

7 голосов
/ 27 февраля 2011

У меня есть 10 слов. Как я могу получить все возможные комбинации из 5 слов (n=10, k=5). Заказ не имеет значения .

Например: "A", "B", "C", if k=2 (n=3 in this case), хотелось бы AB, BC и AC. Может быть, вы знаете какой-нибудь полезный код или пример.

P.S. Извините, если я не достаточно прав, потому что я не очень хорошо знаю английский.

Ответы [ 3 ]

17 голосов
/ 26 июля 2013

То, что вы пытаетесь сделать, - это получить все варианты коллекции.

Вот фрагмент кода: 

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

Выходы: 

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
0 голосов
/ 25 июня 2018

Вот что я собрал: 

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

производит: 

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

Обратите внимание, что это сжато, но неэффективно и должноне должен использоваться для больших наборов или внутренних петель.Примечательно, что короткие массивы восстанавливаются несколько раз и могут быть запомнены, и IEnumerable будет повторяться несколько раз, что может привести к неожиданной работе, если не принять меры.

Кроме того, если вход содержитдублирует, то вывод будет также.Либо сначала используйте .Distinct().ToArray(), либо используйте другое решение, которое включает проверку на равенство и, по-видимому, принимает IEqualityComparer для общности.

0 голосов
/ 17 февраля 2017

А как насчет более функционального решения 

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
...