liste c # permutations avec longueur limitée

Vous ne recherchez pas une permutation, mais une variation. Voici un algorithme possible. Je préfère les méthodes d’iterator pour les fonctions pouvant potentiellement renvoyer de très nombreux éléments. Ainsi, l’appelant peut décider s’il a vraiment besoin de tous les éléments:

 IEnumerable> GetVariations(IList offers, int length) { var startIndices = new int[length]; var variationElements = new HashSet(); //for duplicate detection while (startIndices[0] < offers.Count) { var variation = new List(length); var valid = true; for (int i = 0; i < length; ++i) { var element = offers[startIndices[i]]; if (variationElements.Contains(element)) { valid = false; break; } variation.Add(element); variationElements.Add(element); } if (valid) yield return variation; //Count up the indices startIndices[length - 1]++; for (int i = length - 1; i > 0; --i) { if (startIndices[i] >= offers.Count) { startIndices[i] = 0; startIndices[i - 1]++; } else break; } variationElements.Clear(); } } 

L’idée de cet algorithme est d’utiliser un nombre dans la base offers.Count . Pour trois offres, tous les chiffres sont compris entre 0 et 2. Nous incrémentons ensuite ce nombre étape par étape et nous renvoyons les offres correspondant aux indices spécifiés. Si vous souhaitez autoriser les doublons, vous pouvez supprimer la vérification et le HashSet .

Mettre à jour

Voici une variante optimisée qui effectue la vérification des doublons au niveau de l’index. Dans mes tests, il est beaucoup plus rapide que la variante précédente:

 IEnumerable> GetVariations(IList offers, int length) { var startIndices = new int[length]; for (int i = 0; i < length; ++i) startIndices[i] = i; var indices = new HashSet(); // for duplicate check while (startIndices[0] < offers.Count) { var variation = new List(length); for (int i = 0; i < length; ++i) { variation.Add(offers[startIndices[i]]); } yield return variation; //Count up the indices AddOne(startIndices, length - 1, offers.Count - 1); //duplicate check var check = true; while (check) { indices.Clear(); for (int i = 0; i <= length; ++i) { if (i == length) { check = false; break; } if (indices.Contains(startIndices[i])) { var unchangedUpTo = AddOne(startIndices, i, offers.Count - 1); indices.Clear(); for (int j = 0; j <= unchangedUpTo; ++j ) { indices.Add(startIndices[j]); } int nextIndex = 0; for(int j = unchangedUpTo + 1; j < length; ++j) { while (indices.Contains(nextIndex)) nextIndex++; startIndices[j] = nextIndex++; } break; } indices.Add(startIndices[i]); } } } } int AddOne(int[] indices, int position, int maxElement) { //returns the index of the last element that has not been changed indices[position]++; for (int i = position; i > 0; --i) { if (indices[i] > maxElement) { indices[i] = 0; indices[i - 1]++; } else return i; } return 0; } 

Voici une autre implémentation qui, à mon avis, devrait être plus rapide que la réponse acceptée (et c’est nettement moins de code).

 public static IEnumerable> GetVariationsWithoutDuplicates(IList items, int length) { if (length == 0 || !items.Any()) return new List> { new List() }; return from item in items.Distinct() from permutation in GetVariationsWithoutDuplicates(items.Where(i => !EqualityComparer.Default.Equals(i, item)).ToList(), length - 1) select Prepend(item, permutation); } public static IEnumerable> GetVariations(IList items, int length) { if (length == 0 || !items.Any()) return new List> { new List() }; return from item in items from permutation in GetVariations(Remove(item, items).ToList(), length - 1) select Prepend(item, permutation); } public static IEnumerable Prepend(T first, IEnumerable rest) { yield return first; foreach (var item in rest) yield return item; } public static IEnumerable Remove(T item, IEnumerable from) { var isRemoved = false; foreach (var i in from) { if (!EqualityComparer.Default.Equals(item, i) || isRemoved) yield return i; else isRemoved = true; } } 

Sur mon Core 2 Duo à 3,1 GHz, j’ai testé avec ceci:

 public static void Test(Func, int, IEnumerable>> getVariations) { var max = 11; var timer = System.Diagnostics.Stopwatch.StartNew(); for (int i = 1; i < max; ++i) for (int j = 1; j < i; ++j) getVariations(MakeList(i), j).Count(); timer.Stop(); Console.WriteLine("{0,40}{1} ms", getVariations.Method.Name, timer.ElapsedMilliseconds); } // Make a list that repeats to guarantee we have duplicates public static IList MakeList(int size) { return Enumerable.Range(0, size/2).Concat(Enumerable.Range(0, size - size/2)).ToList(); } 

Non optimisé

 GetVariations 11894 ms GetVariationsWithoutDuplicates 9 ms OtherAnswerGetVariations 22485 ms OtherAnswerGetVariationsWithDuplicates 243415 ms 

Avec optimisations du compilateur

 GetVariations 9667 ms GetVariationsWithoutDuplicates 8 ms OtherAnswerGetVariations 19739 ms OtherAnswerGetVariationsWithDuplicates 228802 ms 

Si je vous ai bien compris, voici ce dont vous avez besoin

cela créera des permutations basées sur la limite de chaîne spécifiée

  public static List> GetPerms(List list, int chainLimit) { if (list.Count() == 1) return new List> { list }; return list .Select((outer, outerIndex) => GetPerms(list.Where((inner, innerIndex) => innerIndex != outerIndex).ToList(), chainLimit) .Select(perms => (new List { outer }).Union(perms).Take(chainLimit))) .SelectMany>, List>(sub => sub.Select, List>(s => s.ToList())) .Distinct(new PermComparer()).ToList(); } class PermComparer : IEqualityComparer> { public bool Equals(List x, List y) { return x.SequenceEqual(y); } public int GetHashCode(List obj) { return (int)obj.Average(o => o.GetHashCode()); } } 

et vous l’appelez comme ça

  List> lst = GetPerms(offers, 2); 

J’ai fait cette fonction est assez générique afin que vous puissiez l’utiliser à d’autres fins

par exemple

  List list = new List(new[] { "apple", "banana", "orange", "cherry" }); List> perms = GetPerms(list, 2); 

résultat