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

Обновить

December 2018

Просмотры

16.3k раз

19

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

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

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

(Не nessesarily в таком порядке)

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

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

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

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

Представьте себе , я назвал , 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;
}

6 ответы

0

You can use this Permute LINQ extension:

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

Which results in this:

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

You can optionally specify the # of permutations

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

Results:

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

Extension Class to add:

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

For the record: Josh's answer the generic way:

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

Here is my Permutation and Combination function using 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);
}

For the DNA alphabet 'A', 'C', 'G', 'T':

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

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

gives

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

and the combinations (k = 2) of DNA alphabet

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

are

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

What you're looking for are actually permutations. In short, permutations means that order is relevant (ie, 12 is different from 21) whereas a combination means order is irrelevant (12 and 21 are equivalent). For more information see Wikipedia.

See this thread.

As for doing is in pure LINQ, that sounds like using LINQ for the sake of using LINQ.

39

For what it's worth, try something like this:

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

As others have pointed out the solutions on this page will generate duplicates if any of the elements are the same. The Distinct() extension will remove them, but it's not very scalable as it will usually result in the entire search tree being traversed anyway. You'll trim the search space considerably by invoking it during traversal:

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

For the example string "bananabana" this results in 8,294 nodes being visited, as opposed to the 9,864,101 visited when you don't do traversal culling.