¿Cómo generar un conjunto potencia de un conjunto dado?

Te damos la bienvenida a nuestra página web, aquí encontrarás la respuesta de lo que buscabas.

Solución:

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

No es la definición más amigable del mundo, pero un ejemplo ayudará:

P.ej. por 1, 2los subconjuntos son : , 1, 2, 1, 2

Por lo tanto, el conjunto de potencias es , 1, 2, 1, 2

---

Para generar el conjunto potencia, observe cómo crea un subconjunto: va a cada elemento uno por uno y luego lo retiene o lo ignora.

Que esta decisión sea indicada por un bit (1/0).

Así, para generar 1elegirás 1 Y cae 2 (10).

En líneas similares, puede escribir un vector de bits para todos los subconjuntos:

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

Para reiterar: Un subconjunto si se forma incluyendo algunos o todos los elementos del conjunto original. Por lo tanto, para crear un subconjunto, vaya a cada elemento y luego decida si mantenerlo o eliminarlo. Esto significa que para cada elemento, tienes 2 decisiones. Por lo tanto, para un conjunto, puede terminar con 2^N diferentes decisiones, correspondientes a 2^N diferentes subconjuntos.

A ver si puedes recogerlo desde aquí.

Cree un conjunto de poder de: "A", "B", "C".

---

Pseudocódigo:

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

val sets = 

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

---

Explicación del algoritmo:

1) Inicializar sets a un conjunto vacío: .

2) Iterar sobre cada elemento en "A", "B", "C"

3) Iterar sobre cada set en tus sets.

3.1) Crear un nuevo conjunto que sea una copia de set.

3.2) Anexar el item hacia new set.

3.3) Anexar el new set para sets.

4) Añadir el item para usted sets.

4) La iteración está completa. Agregue el conjunto vacío a su resultSets.

---

Tutorial:

Veamos el contenido de sets después de cada iteración:

Iteración 1, elemento = “A”:

sets = "A"

Iteración 2, elemento = “B”:

sets = "A", "A", "B", "B"

Iteración 3, elemento = “C”:

sets = "A", "A", "B", "B", "A", "C", "A", "B", "C", "B", "C", "C"

Iteración completa, agregue un conjunto vacío:

sets = "A", "A", "B", "B", "A", "C", "A", "B", "C", "B", "C", "C", 

El tamaño de los conjuntos es 2^|conjunto| = 2^3 = 8 que es correcto.

---

Ejemplo de implementación en Java:

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

Aporte: [A, B, C]

Producción: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]

El conjunto de potencia es solo un conjunto de todos los subconjuntos para un conjunto dado. Incluye todos los subconjuntos (con conjunto vacío). Es bien sabido que hay 2^norte elementos de este conjunto, donde N es el recuento de elementos en el conjunto original.

Para construir un conjunto de potencia, se puede usar lo siguiente:

• Cree un ciclo, que repita todos los enteros desde 0 hasta 2^norte-1
• Proceder a la representación binaria para cada entero
• Cada representación binaria es un conjunto de N bits (para números menores, agregue ceros a la izquierda). Cada bit corresponde, si el determinado miembro del conjunto está incluido en el subconjunto actual.

Ejemplo, 3 números: a, b, c

number binary  subset
0      000      
1      001      c
2      010      b
3      011      b,c
4      100      a
5      101      a,c
6      110      a,b
7      111      a,b,c

Aquí puedes ver las comentarios y valoraciones de los usuarios

---

---

Utiliza Nuestro Buscador