Комбинированный генератор в Linq

Ответ 1

Для чего стоит, попробуйте что-то вроде этого:

public static IEnumerable<string> GetPermutations(string s)
{
    if (s.Length > 1)
        return from ch in s
               from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1))
               select string.Format("{0}{1}", ch, permutation);

    else
        return new string[] { s };
}

Ответ 2

Для записи: Джош ответит на общий путь:

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items) {
        if (items.Count() > 1) {
            return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))),
                                   (item, permutation) => new[] { item }.Concat(permutation));
        } else {
            return new[] {items};
        }
    }

Ответ 3

Вот моя функция Permutation and Combination с использованием Linq

public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
{
    if (source == null)
        throw new ArgumentNullException("source");

    yield return item;

    foreach (var element in source)
        yield return element;
}

public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();

    if (list.Count > 1)
        return from s in list
                from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                select p.Prepend(s);

    return new[] { list };
}

public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
{
    if (source == null)
        throw new ArgumentNullException("source");

    var list = source.ToList();
    if (k > list.Count)
        throw new ArgumentOutOfRangeException("k");

    if (k == 0)
        yield return Enumerable.Empty<TSource>();

    foreach (var l in list)
        foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1))
            yield return c.Prepend(l);
}

Для алфавита ДНК "A", "C", "G", "T":

var dna = new[] {'A', 'C', 'G', 'T'};

foreach (var p in dna.Permutate())
    Console.WriteLine(String.Concat(p));

дает

ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA

и комбинации (k = 2) алфавита ДНК

foreach (var c in dna.Combinate(2))
        Console.WriteLine(String.Concat(c));

являются

AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT

Ответ 4

То, что вы ищете, это перестановки. Короче говоря, перестановки означают, что порядок имеет значение (т.е. 12 отличается от 21), тогда как порядок комбинаций не имеет значения (12 и 21 эквивалентны). Для получения дополнительной информации см. Wikipedia.

Смотрите этот поток.

Что касается выполнения в чистом LINQ, это похоже на использование LINQ для использования LINQ.

Ответ 5

Как указывали другие, решения на этой странице будут генерировать дубликаты, если какой-либо из этих элементов одинаковый. Расширение Distinct() удалит их, но оно не очень масштабируемо, так как это, как правило, приведет к тому, что все дерево поиска будет проходить в любом случае. Вы значительно урезаете пространство поиска, вызвав его во время обхода:

private static IEnumerable<string> Permute(string str)
{
    if (str.Length == 0)
        yield return "";
    else foreach (var index in str.Distinct().Select(c => str.IndexOf(c)))
        foreach (var p in Permute(str.Remove(index, 1)))
            yield return str[index] + p;
}

В примере строки "bananabana" это приводит к посещению 8 294 узлов, в отличие от 9 864 101 посещенных, когда вы не выполняете обход.