Cómo imprimir el conjunto de potencia de un conjunto finito de enteros en Java usando recursividad

Esto es un poco exagerado, pero es un método de utilidad que escribí hace un tiempo que devuelve el conjunto de potencia para un conjunto dado. Dado que construye un conjunto de potencia real, tendrá un límite inferior para el tamaño del conjunto que puede manejar en una cantidad dada de memoria.

A propósito no usa la recursividad, porque eso usa aún más memoria. Esto se puede escribir de forma algo más compacta usando la recursividad.

Incluso incluiré los comentarios. 🙂

/ **
* Devuelve un conjunto que contiene todos los subconjuntos posibles para un superconjunto dado.
*

* Ejemplo:

* El resultado para el conjunto {A, B, C} es {{}, {A}, {B}, {C}, {A, B},
* {A, C}, {B, C}, {A, B, C}} .
* *
* @param el tipo de elementos en el conjunto devuelto
* @param establece el superconjunto
* @ devolver el conjunto de subconjuntos. El tamaño del conjunto devuelto es 2 ^ set.size () .
* /
public static Set > powerSet (Set set) {
final int setSize = set.size ();
final int powerSize = (int) Math.pow (2, setSize);
@SuppressWarnings (“sin marcar”)
conjunto final [] sets = new LinkedHashSet [powerSize]; // conjunto de conjuntos para acceso indexado

// asigna subconjuntos de tamaño correcto
// comienza desde el último subconjunto de potencia, que contiene todos los elementos en
establece [0] = nuevo LinkedHashSet (0); // un conjunto mutable vacío
for (int ii = powerSize – 1; ii> 0; ii – = 2) {// todos los subconjuntos impares obtienen el primer elemento E (1)
// sets [ii] es el último set de la serie E (1), S (1) …
// donde S (1) … es el conjunto (posiblemente vacío) de elementos restantes en la serie
// sets [ii-1] es S (1) … que es el set anterior de la serie
// mientras S (n) … no está vacío, la serie continúa retrocediendo al eliminar el siguiente
// elemento en el conjunto E (n + 1), S (n + 1) …
int groupSize = 1;
int ss = ii;
Establecer subSet;
// regresa la serie hasta que se encuentra un conjunto asignado
while ((subSet = sets [ss – = groupSize]) == null)
groupSize * = 2;
int ssSize = subSet.size (); // obtener el tamaño del conjunto asignado más pequeño de esta serie
hacer {
establece [ss + = groupSize] = nuevo LinkedHashSet (++ ssSize); // cada conjunto en serie es +1
groupSize / = 2;
} while (ss! = ii);
}

// para cada elemento en el superconjunto
int groupSize = 1;
para (elemento T: conjunto) {
// para cada grupo de subconjuntos
int ii = groupSize;
hacer {
// agrega un elemento de superconjunto a los subconjuntos a los que pertenece
for (int end = ii + groupSize; ii establece [ii] .add (elemento);
ii + = groupSize;
} while (ii groupSize * = 2;
}

volver al conjunto (conjuntos);
}

/ **
* Devuelve un conjunto modificable que contiene los elementos proporcionados. Si elements es
* null luego se devuelve un conjunto vacío.
* *
* @param el tipo de elementos en el conjunto devuelto
* @param elements los elementos establecidos
* @ devolver un {@link Set} que contenga elementos
* /
public static Set toSet (T … elements) {
Establezca result = new LinkedHashSet (elements == null? 0: elements.length);
if (elementos! = nulo)
Collections.addAll (resultado, elementos);
resultado de retorno;
}

Entonces, utilizando ese método, puede imprimir el conjunto devuelto.