Kombination Generator in Linq

Question

Ist es möglich, einige Linq zu erstellen, die eine Liste mit allen möglichen Kombinationen von einer Reihe von Zahlen erzeugt ??

Wenn Sie „21“ eingeben würde es eine Liste mit den Elementen erzeugen:

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

(nicht nessesarily in dieser Reihenfolge)

Ich verstehe Sie Bereich Dinge zu tun, können wie:

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

Welche erzeugt das Alphabet von A-Z. Aber ich kann nicht scheinen, dieses Wissen zu übertragen, eine Kombination Generator machen

Ich konnte es mit dem folgenden Code, um herauszufinden, aber es scheint viel zu sperrig und ich bin sicher, kann es mit einem paar Zeilen durchgeführt werden. Es ist wirklich das Gefühl, wie eine schlechte Lösung, die ich gemacht habe.

Stellen Sie sich vor ich GetAllCombinations("4321") genannt haben, wenn es hilft

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

Für das, was es wert ist, versuchen, etwas wie folgt aus:

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

Für das Protokoll: Joshs die allgemeine Art und Weise beantworten:

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

Hier ist meine Permutation und Kombination Funktion 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);
}

Für das DNA-Alphabet 'A', 'C', 'G', 'T':

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

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

gibt

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

und die Kombinationen (k = 2) von DNA-Alphabet

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

sind

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

Answer 4

Was Sie suchen sind tatsächlich Permutationen. Kurz gesagt, bedeutet, Permutationen, die Reihenfolge relevant ist (dh, 12 unterscheidet sich von 21), während eine Kombination bedeutet Reihenfolge irrelevant ist (12 und 21 äquivalent sind). Weitere Informationen finden Sie Wikipedia.

Siehe .

Was tut, ist in reiner LINQ, die zum Zweck der Verwendung von LINQ wie mit LINQ klingt.

Answer 5

Wie andere haben die Lösungen auf dieser Seite darauf hingewiesen werden Duplikate erzeugen, wenn eine der Elemente gleich sind. Die Distinct () Erweiterung wird entfernen Sie sie, aber es ist nicht sehr skalierbar, da sie in der Regel in der gesamten Suchbaum ohnehin durchlaufen führen wird. Sie werden den Suchraum trimmen erheblich, indem sie es während Traversal Aufruf:

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

Für das Beispiel string „bananabana“ führt dies zu 8294 Knoten besucht wird, in Bezug auf die besuchten 9.864.101 Gegensatz, wenn Sie das nicht tun Traversal Culling.

Answer 6

Sie können diese Vertausche LINQ-Erweiterung verwenden:

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

Welche Ergebnisse in dieser:

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

Sie können optional die Anzahl der Permutationen angeben

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

Ergebnisse:

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

Erweiterung der Klasse hinzuzufügen:

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