Génération de permutations à l'aide de LINQ

Si je comprends la question: vous êtes à la recherche pour l'ensemble des séquences d'entiers de longueur P, où chaque entier dans le jeu est entre 0 et T, et la séquence est monotone nondecreasing. Est-ce exact?

La rédaction d'un tel programme à l'aide d'un itérateur blocs est simple:

using System;
using System.Collections.Generic;
using System.Linq;

static class Program
{
    static IEnumerable<T> Prepend<T>(T first, IEnumerable<T> rest)
    {
        yield return first;
        foreach (var item in rest)
            yield return item;
    }

    static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
    {
        if (p == 0)
            yield return Enumerable.Empty<int>();
        else
            for (int first = t1; first <= t2; ++first)
                foreach (var rest in M(p - 1, first, t2))
                    yield return Prepend(first, rest);
    }

    public static void Main()
    {
        foreach (var sequence in M(4, 0, 2))
            Console.WriteLine(string.Join(", ", sequence));
    }
}

Qui produit le résultat désiré: nondecreasing séquences de longueur 4 tirées de 0 à 2.

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 1, 1
0, 0, 1, 2
0, 0, 2, 2
0, 1, 1, 1
0, 1, 1, 2
0, 1, 2, 2
0, 2, 2, 2
1, 1, 1, 1
1, 1, 1, 2
1, 1, 2, 2
1, 2, 2, 2
2, 2, 2, 2

Notez que l'utilisation de multiplier imbriquées les itérateurs pour la concaténation est pas très efficacemais qui s'en soucie? Vous êtes déjà plus de générer un exponentielle nombre de séquences, de sorte que le fait qu'il y a un polynôme inefficacité dans le générateur est sans importance.

La méthode M génère tous monotone nondecreasing séquences d'entiers de longueur p, où les entiers sont entre t1 et t2. Il le fait de manière récursive, à l'aide d'un simple récursivité. Le cas de base est qu'il y a exactement une séquence de longueur zéro, à savoir la séquence vide. La récursivité est le cas pour calculer, disons P = 3, t1 = 0, t2 = 2, permet de calculer:

- all sequences starting with 0 followed by sequences of length 2 drawn from 0 to 2.
- all sequences starting with 1 followed by sequences of length 2 drawn from 1 to 2.
- all sequences starting with 2 followed by sequences of length 2 drawn from 2 to 2.

Et voilà le résultat.

Alternativement, vous pouvez utiliser la requête des compréhensions à la place de l'itérateur de blocs dans la principale méthode récursive:

static IEnumerable<T> Singleton<T>(T first)
{
    yield return first;
}

static IEnumerable<IEnumerable<int>> M(int p, int t1, int t2)
{
    return p == 0 ?

        Singleton(Enumerable.Empty<int>()) : 

        from first in Enumerable.Range(t1, t2 - t1 + 1)
        from rest in M(p - 1, first, t2)
        select Prepend(first, rest);
}

Qui fait la même chose; il déplace juste les boucles dans le SelectMany méthode.

1. créer un autre tableau de taille 2^n, où n est le nombre de produits
2. compter en binaire de 0 à 2^n et de remplir le tableau avec chaque chef d'accusation. par exemple, si n=3
   le tableau ressemble à ceci :

000 001 010 011 100 101 110 111

1. boucle à travers le tableau binaire et de trouver celles qui sont dans chaque numéro, puis ajouter le produit avec le même index:

 for each binaryNumber in ar{
   for i = 0 to n-1{
     if binaryNumber(i) = 1
       permunation.add(products(i))
   }
  permunations.add(permutation) 
}

exemple:
si binaryNumber= 001 puis permunation1 = produit1
si binaryNumber= 101 puis permunation1 = product3,produit1

Aujourd'hui, je suis tombé sur ce et pensé que je pourrais partager mon œuvre.

Pour tous les entiers compris entre N et M, vous devez faire un tableau en premier:

IEnumerable<int> Range(int n, int m) {
for(var i = n; i < m; ++i) {
yield return i;
}
}

et le lancer à travers Permutations(Range(1, 10)):

    enum PermutationsOption {
None,
SkipEmpty,
SkipNotDistinct
}
private IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> elements, PermutationsOption option = PermutationsOption.None, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
var elementsList = new List<IEnumerable<T>>();
var elementsIndex = 0;
var elementsCount = elements.Count();
var elementsLength = Math.Pow(elementsCount + 1, elementsCount);
if (option.HasFlag(PermutationsOption.SkipEmpty)) {
elementsIndex = 1;
}
if (elements.Count() > 0) {
do {
var elementStack = new Stack<T>();
for (var i = 0; i < elementsCount; ++i) {
var ind = (int)(elementsIndex / Math.Pow(elementsCount + 1, i) % (elementsCount + 1));
if (ind == 0) {
continue;
}
elementStack.Push(elements.ElementAt(ind - 1));
}
var elementsCopy = elementStack.ToArray() as IEnumerable<T>;
if (option.HasFlag(PermutationsOption.SkipNotDistinct)) {
elementsCopy = elementsCopy.Distinct();
elementsCopy = elementsCopy.ToArray();
if (elementsList.Any(p => CompareItemEquality(p, elementsCopy, equalityComparer))) {
continue;
}
}
elementsList.Add(elementsCopy);
} while (++elementsIndex < elementsLength);
}
return elementsList.ToArray();
}
private bool CompareItemEquality<T>(IEnumerable<T> elements1, IEnumerable<T> elements2, IEqualityComparer<T> equalityComparer = default(IEqualityComparer<T>)) {
if (equalityComparer == null) {
equalityComparer = EqualityComparer<T>.Default;
}
return (elements2.Count() == elements2.Count()) && (elements2.All(p => elements1.Contains(p, equalityComparer)));
}

    public static IList<IList<T>> Permutation<T>(ImmutableList<ImmutableList<T>> dimensions)
{
IList<IList<T>> result = new List<IList<T>>();
Step(ImmutableList.Create<T>(), dimensions, result);
return result;
}
private static void Step<T>(ImmutableList<T> previous, 
ImmutableList<ImmutableList<T>> rest, 
IList<IList<T>> result)
{
if (rest.IsEmpty)
{
result.Add(previous);
return;
}
var first = rest[0];
rest = rest.RemoveAt(0);
foreach (var label in first)
{
Step(previous.Add(label), rest, result);
}
}