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

Question

Можно ли создать какой-нибудь Linq, который генерирует список, содержащий все возможные комбинации серии чисел?

Если вы введете «21», будет создан список с элементами:

list[0] = "21"
list[1] = "22"
list[2] = "11"
list[3] = "12"

(Не обязательно в этом порядке)

Я понимаю, что вы можете использовать диапазон для таких вещей, как:

List<char> letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations

, который генерирует алфавит из a-z. Но я не могу передать эти знания, чтобы сделать комбинационный генератор

Мне удалось выяснить это с помощью следующего кода, но он кажется слишком громоздким, и я уверен, что это можно сделать с помощью нескольких строк. Это действительно плохое решение, которое я принял.

Представьте, что я позвонил GetAllCombinations("4321"), если это поможет

public static String[] GetAllCombinations(String s)
{
    var combinations = new string[PossibleCombinations(s.Length)];

    int n = PossibleCombinations(s.Length - 1);

    for (int i = 0; i < s.Length; i++)
    {
        String sub;
        String[] subs;

        if (i == 0)
        {
            sub = s.Substring(1); //Get the first number
        }
        else if (i == s.Length - 1)
        {
            sub = s.Substring(0, s.Length - 1);
        }
        else
        {
            sub = s.Substring(0, i) + s.Substring(i + 1); 
        }

        subs = GetAllCombinations(sub);

        for (int j = 0; j < subs.Length; j++)
        {
            combinations[i * n + j] = s[i] + subs[j];
        }
    }

    return combinations;
}
public static int PossibleCombinations(int n) //Combination possibilities. e.g 1-2-3-4 have 24 different combinations
{
    int result = 1;

    for (int i = 1; i <= n; i++)
        result *= i;

    return result;
}

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

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

Answer 3

Вот моя функция перестановок и комбинаций с использованием 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

Answer 4

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

См. эту тему.

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

Answer 5

Вы можете использовать это расширение Permute LINQ:

foreach (var value in Enumerable.Range(1,3).Permute())
  Console.WriteLine(String.Join(",", value));

Что приводит к этому:

1,1,1
1,1,2
1,1,3
1,2,1
1,2,2
1,2,3
1,3,1
1,3,2
1,3,3
2,1,1
2,1,2
2,1,3
2,2,1
2,2,2
2,2,3
2,3,1
...

При желании можно указать количество перестановок

foreach (var value in Enumerable.Range(1,2).Permute(4))
  Console.WriteLine(String.Join(",", value));

Результаты:

1,1,1,1
1,1,1,2
1,1,2,1
1,1,2,2
1,2,1,1
1,2,1,2
1,2,2,1
1,2,2,2
2,1,1,1
2,1,1,2
2,1,2,1
2,1,2,2
2,2,1,1
2,2,1,2
2,2,2,1
2,2,2,2

Добавочный класс для добавления:

public static class IEnumberableExtensions
{
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, values.Count() - 1));
  public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> values, int permutations) => values.SelectMany(x => Permute(new[] { new[] { x } }, values, permutations - 1));
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values, int count) => (count == 1) ? Permute(current, values) : Permute(Permute(current, values), values, --count);
  private static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<IEnumerable<T>> current, IEnumerable<T> values) => current.SelectMany(x => values.Select(y => x.Concat(new[] { y })));
}

Answer 6

Как уже отмечали другие, решения на этой странице будут генерировать дубликаты, если какой-либо из элементов будет одинаковым. Расширение 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 посещений, когда вы не выполняете выборочный обход.