Générateur combiné à Linq

Question

Est-il possible de créer une Linq qui génère une liste contenant toutes les combinaisons possibles d'une série de nombres ??

Si vous entrez « 21 » il générerait une liste avec les éléments:

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

(Non nessesarily dans cet ordre)

Je comprends que vous pouvez utiliser gamme pour faire des choses comme:

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

qui génère l'alphabet de A-Z. Mais je ne peux pas sembler transférer ce savoir faire un générateur de combinaison

Je suis en mesure de le comprendre avec le code suivant, mais il semble trop encombrant et je suis sûr qu'il peut être fait avec quelques lignes. Il ne se sent vraiment comme une mauvaise solution que je l'ai fait.

Imaginez que je l'ai appelé GetAllCombinations("4321") si elle aide

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

Pour ce que ça vaut la peine, essayer quelque chose comme ceci:

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

Pour mémoire: Josh répondre à la manière générique:

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

Voici ma fonction Permutation et combinaison 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);
}

Pour l'alphabet d'ADN 'A', 'C', 'G', 'T':

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

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

donne

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

et les combinaisons (k = 2) de l'alphabet de l'ADN

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

sont

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

Answer 4

Qu'est-ce que vous cherchez sont en fait des permutations. En bref, les permutations signifie que l'ordre est pertinent (par exemple, 12 est différent de 21), tandis que la combinaison des moyens de commande est sans importance (12 et 21 sont équivalentes). Pour plus d'informations, consultez Wikipedia.

Voir ce fil.

Quant à faire est dans le plus pur LINQ, qui sonne comme LINQ pour le bien d'utiliser LINQ.

Answer 5

Comme d'autres l'ont souligné les solutions sur cette page va générer des doublons si des éléments sont les mêmes. Le Distinct () extension les enlever, mais ce n'est pas très évolutive car elle entraîne généralement l'arbre de recherche entier étant traversé de toute façon. Vous découpez considérablement l'espace de recherche en invoquant pendant 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;
}

Pour l'exemple chaîne « bananabana » cela se traduit par 8.294 noeuds visités, par opposition à la 9864101 lorsque vous ne visité faites pas culling traversal.

Answer 6

Vous pouvez utiliser cette extension Permute LINQ:

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

Ce qui se traduit par ceci:

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

Vous pouvez spécifier le nombre de permutations

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

Résultats:

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

Classe d'extension à ajouter:

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