Comment générer une puissance d'un groupe donné?

Power set of a set A is the set of all of the subsets of A.

Pas le plus sympathique de la définition dans le monde, mais un exemple pour vous aider :

Par exemple. pour {1, 2}, sont les sous-ensembles : {}, {1}, {2}, {1, 2}

Ainsi, la puissance est {{}, {1}, {2}, {1, 2}}

---

Pour générer de la puissance, d'observer comment vous créez un sous-ensemble : vous allez à chaque élément un par un, puis de les conserver ou de les ignorer.

Laissez-la présente décision sera indiqué par un bit (1/0).

Ainsi, pour générer {1}, vous allez choisir 1 et déposez 2 (10).

Sur les mêmes lignes, vous pouvez écrire un vecteur de bits pour tous les sous-ensembles :

• {} -> 00
  
  {1} -> 10
  
  {2} -> 01
  
  {1,2} -> 11

À rappeler : Un sous-ensemble si elle est formée par dont certains ou tous les éléments de l'ensemble original. Ainsi, pour créer un sous-ensemble, vous allez à chaque élément, et ensuite décider de les garder ou de le rejeter. Cela signifie que pour chaque élément, vous avez 2 décisions. Ainsi, pour un ensemble, vous pouvez vous retrouver avec 2^N des décisions différentes, correspondant à 2^N différents sous-ensembles.

Voir si vous pouvez le récupérer à partir d'ici.

OriginalL'auteur axiom

Créer un power-set de: {"A", "B", "C"}.

---

Pseudo-code:

val set = {"A", "B", "C"}

val sets = {}

for item in set:
  for set in sets:
    sets.add(set + item)
  sets.add({item})
sets.add({})

---

Algorithme explication:

1) Initialiser sets à un ensemble vide: {}.

2) Itérer sur chaque élément dans {"A", "B", "C"}

3) Itérer sur chaque set dans votre sets.

3.1) Créer un nouveau jeu qui est une copie de set.

3.2), Ajoutez le item à la new set.

3.3), Ajoutez le new set à sets.

4) Ajouter le item à votre sets.

4) Itération est terminée. Ajouter l'ensemble vide pour votre resultSets.

---

Procédure pas à pas:

Regardons le contenu de sets après chaque itération:

À l'itération 1, item = "A":

sets = {{"A"}}

Itération 2, item = "B":

sets = {{"A"}, {"A", "B"}, {"B"}}

Itération 3, item = "C":

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}

Itération complète, ajouter de l'ensemble vide:

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}

La taille des ensembles de est 2^|set| = 2^3 = 8, ce qui est correct.

---

Exemple d'implémentation en Java:

public static <T> List<List<T>> powerSet(List<T> input) {
  List<List<T>> sets = new ArrayList<>();
  for (T element : input) {
    for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
      List<T> newSet = new ArrayList<>(setsIterator.next());
      newSet.add(element);
      setsIterator.add(newSet);
    }
    sets.add(new ArrayList<>(Arrays.asList(element)));
  }
  sets.add(new ArrayList<>());
  return sets;
}

D'entrée: [A, B, C]

De sortie: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]

OriginalL'auteur Cristian

Générant toutes les combinaison d'un ensemble (En incluant ou non un élément).
expliquer par exemple:
3 éléments dans un ensemble (ou une liste). La possible sous-ensemble sera:

000   
100   
010   
001
110
101
011
111   

Le résultat est de 2^(nombre d'éléments de l'ensemble).

En tant que tel, nous pouvons générer toutes les combinaisons de N éléments (avec python) comme suit:

def powerSet(items):

    N = len(items)

    for i in range(2**N):

        comb=[]
        for j in range(N):
            if (i >> j) % 2 == 1:
                comb.append(items[j])
        yield comb

for x in powerSet([1,2,3]):
    print (x)

OriginalL'auteur Amjad

Exemple De Code Java:

void printPowerSetHelper(String s, String r) {
    if (s.length() > 0) {
        printPowerSetHelper(s.substring(1), r + s.charAt(0));
        printPowerSetHelper(s.substring(1), r);
    } 
    if (r.length() > 0) System.out.println(r);
}

void printPowerSet(String s) {
    printPowerSetHelper(s,"");
}

OriginalL'auteur ashwanilabs