Création d’un ensemble de puissance d’une séquence

L’ensemble de puissance est facile à générer si l’on connaît les bits. Pour l’ensemble des N éléments, il y aura 2^N sous-ensembles qui iront à l’ensemble de puissance (y compris l’ensemble vide et l’ensemble initial). Donc, chaque élément sera soit IN ou OUT ( 1 ou 0 en d’autres termes). Compte tenu de cela, il est facile de représenter des sous-ensembles de l’ensemble sous forme de masques binarys. En énumérant tous les masques de bits possibles, il est possible de construire l’ensemble des jeux de puissances. Pour ce faire, nous devons examiner chaque bit dans le masque de bits et prendre un élément du jeu d’entrées s’il y en a 1 à cet endroit. Vous trouverez ci-dessous un exemple de ssortingng (collection de caractères) en entrée. Il peut être facilement réécrit pour fonctionner pour la collecte de toutes les valeurs de type.

 private static List PowerSet(ssortingng input) { int n = input.Length; // Power set contains 2^N subsets. int powerSetCount = 1 << n; var ans = new List(); for (int setMask = 0; setMask < powerSetCount; setMask++) { var s = new StringBuilder(); for (int i = 0; i < n; i++) { // Checking whether i'th element of input collection should go to the current subset. if ((setMask & (1 << i)) > 0) { s.Append(input[i]); } } ans.Add(s.ToSsortingng()); } return ans; } 

Exemple

Supposons que vous ayez la chaîne "xyz" en entrée, elle contient 3 éléments, puis 2^3 == 8 éléments dans le jeu de puissances. Si vous effectuez une itération de 0 à 7 vous obtiendrez le tableau suivant. Colonnes: (entier de 10 bases; représentation en bits (base de 2); sous-ensemble du jeu initial).

 0 000 ... 1 001 ..z 2 010 .y. 3 011 .yz 4 100 x.. 5 101 xz 6 110 xy. 7 111 xyz 

Vous pouvez remarquer que la troisième colonne contient tous les sous-ensembles de la chaîne initiale "xyz"

Une autre approche (deux fois plus rapide) et une implémentation générique

Inspiré par l’idée d’Eric, j’ai implémenté une autre variante de cet algorithme (sans bits maintenant). Aussi je l’ai fait générique. Je crois que ce code est proche du plus rapide de ce qui peut être écrit pour le calcul de Power Set. Sa complexité est la même que pour l’approche des bits O(n * 2^n) , mais pour cette approche, la constante est divisée par deux.

 public static T[][] FastPowerSet(T[] seq) { var powerSet = new T[1 << seq.Length][]; powerSet[0] = new T[0]; // starting only with empty set for (int i = 0; i < seq.Length; i++) { var cur = seq[i]; int count = 1 << i; // doubling list each time for (int j = 0; j < count; j++) { var source = powerSet[j]; var destination = powerSet[count + j] = new T[source.Length + 1]; for (int q = 0; q < source.Length; q++) destination[q] = source[q]; destination[source.Length] = cur; } } return powerSet; } 

L’approche de SergeyS est parfaitement raisonnable. Voici une autre façon de penser.

Pour les besoins de cette réponse, je vais supposer que les “ensembles” sont des séquences finies.

Nous définissons la fonction P récursivement comme suit.

• Un ensemble est soit vide, soit un seul élément H suivi d’un ensemble T.
• P(empty) --> { empty }
• P(H : T) --> l’union de P(T) et de chaque élément de P(T) précédé de H

Essayons ça. Quelle est la puissance de {Apple, Banana, Cherry} ?

Ce n’est pas un jeu vide, donc le jeu de puissance de {Apple, Banana, Cherry} est le jeu de puissance de {Banana, Cherry} , plus les jeux formés en ajoutant un préfixe à chacun d’eux.

Nous avons donc besoin de connaître le pouvoir de {Banana, Cherry} . C’est le jeu de puissance de {Cherry} auquel s’ajoute un jeu de préfixe Banana .

Nous avons donc besoin de connaître la puissance de {Cherry} . Il s’agit de l’ensemble de puissance de l’ensemble vide, plus les ensembles formés en ajoutant à chaque Cherry .

Nous avons donc besoin de connaître l’ensemble de puissance de l’ensemble vide. C’est l’ensemble contenant l’ensemble vide. { {} }

Maintenant, ajoutez chaque élément à Cherry et prenez l’union. C’est { {Cherry}, {} } . Cela nous donne le pouvoir de { Cherry } . Rappelez-vous que nous avions besoin de cela pour trouver le pouvoir de {Banana, Cherry} . Nous le fusionnons donc avec la Banana préfixée à chacun et obtenons { {Banana, Cherry}, {Banana}, {Cherry}, {}} de {Banana, Cherry} .

Maintenant, nous avions besoin de cela pour obtenir le jeu de puissance de {Apple, Banana, Cherry} , afin de l’unir à Apple ajouté à chacun et nous avons { {Apple, Banana, Cherry}, {Apple, Banana}, {Apple, Cherry}, {Apple}, {Banana, Cherry}, {Banana}, {Cherry}, {}} et nous avons terminé.

Le code devrait être simple à écrire. Nous aurons d’abord besoin d’une méthode d’aide:

 static IEnumerable Prepend(this IEnumerable tail, T head) { yield return head; foreach(T item in tail) yield return item; } 

Et maintenant, le code est une traduction directe de la description de l’algorithme:

 static IEnumerable> PowerSet(this IEnumerable items) { if (!items.Any()) yield return items; // { { } } else { var head = items.First(); var powerset = items.Skip(1).PowerSet().ToList(); foreach(var set in powerset) yield return set.Prepend(head); foreach(var set in powerset) yield return set; } } 

Avoir un sens?

———– METTRE À JOUR —————-

Sergey souligne à juste titre que mon code utilise un algorithme Schlemiel the Painter et consum donc énormément de temps et de mémoire; bonne prise Sergey. Voici une version efficace qui utilise une stack immuable:

 class ImmutableList { public static readonly ImmutableList Empty = new ImmutableList(null, default(T)); private ImmutableList(ImmutableList tail, T head) { this.Head = head; this.Tail = tail; } public T Head { get; private set; } public ImmutableList Tail { get; private set; } public ImmutableList Push(T head) { return new ImmutableList(this, head); } public IEnumerable> PowerSet() { if (this == Empty) yield return this; else { var powerset = Tail.PowerSet(); foreach (var set in powerset) yield return set.Push(Head); foreach (var set in powerset) yield return set; } } } 

Le même algorithme, SergeyS, mentionne l’utilisation de Linq (où inputSet est l’entrée et outputPowerSet est la sortie):

 int setLength = inputSet.Count; int powerSetLength = 1 << setLength; for (int bitMask = 0; bitMask < powerSetLength; bitMask++) { var subSet = from x in inputSet where ((1 << inputSet.IndexOf(x)) & bitMask) != 0 select x; outputPowerSet.Add(subSet.ToList()); } 

Très tard dans le jeu, mais pourquoi pas l’approche ci-dessous? Cela semble beaucoup plus simple que les suggestions affichées ici:

  /* Description for a sample set {1, 2, 2, 3}: Step 1 - Start with {}: {} Step 2 - "Expand" previous set by adding 1: {} --- {1} Step 3 - Expand previous set by adding the first 2: {} {1} --- {2} {1,2} Step 4 - Expand previous set by adding the second 2: {} {1} {2} {1,2} --- {2} {1,2} {2,2} {1,2,2} Step 5 - Expand previous set by adding 3: {} {1} {2} {1,2} {2} {1,2} {2,2} {1,2,2} --- {3} {1,3} {2,3} {1,2,3} {2,3} {1,2,3} {2,2,3} {1,2,2,3} Total elements = 16 (ie 2^4), as expected. */ private static void PowerSet(IList nums, ref IList> output) { // ToDo: validate args output.Add(new List()); ExpandSet(nums, 0, ref output); } private static void ExpandSet(IList nums, int pos, ref IList> output) { if (pos == nums.Count) { return; } List tmp; int item = nums[pos]; for (int i = 0, n = output.Count; i < n; i++) { tmp = new List(); tmp.AddRange(output[i]); tmp.Add(item); output.Add(tmp); } ExpandSet(nums, pos + 1, ref output); }