Obteniendo un conjunto de poder de un conjunto en Java

El conjunto de poder de {1, 2, 3} es:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Digamos que tengo un Set en Java:

 Set mySet = new HashSet(); mySet.add(1); mySet.add(2); mySet.add(3); Set<Set> powerSet = getPowerset(mySet); 

¿Cómo escribo la función getPowerset, con el mejor orden posible de complejidad? (Creo que podría ser O (2 ^ n).)

Sí, es O(2^n) hecho, ya que necesita generar, bueno, 2^n combinaciones posibles. Aquí hay una implementación en funcionamiento, usando generics y conjuntos:

 public static  Set> powerSet(Set originalSet) { Set> sets = new HashSet>(); if (originalSet.isEmpty()) { sets.add(new HashSet()); return sets; } List list = new ArrayList(originalSet); T head = list.get(0); Set rest = new HashSet(list.subList(1, list.size())); for (Set set : powerSet(rest)) { Set newSet = new HashSet(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); } return sets; } 

Y una prueba, dada su entrada de ejemplo:

  Set mySet = new HashSet(); mySet.add(1); mySet.add(2); mySet.add(3); for (Set s : SetUtils.powerSet(mySet)) { System.out.println(s); } 

De hecho, he escrito un código que hace lo que estás pidiendo en O (1). La pregunta es qué piensas hacer con el Set siguiente. Si va a llamar a size() , es O (1), pero si va a iterar, obviamente es O(2^n) .

contains() sería O(n) , etc.

¿Realmente necesitas esto?

EDITAR:

Este código ahora está disponible en Guava , expuesto a través del método Sets.powerSet(set) .

Aquí hay una solución donde uso un generador, la ventaja es que el conjunto de potencia completo nunca se almacena a la vez … De modo que puede iterar uno por uno sin necesidad de almacenarlo en la memoria. Me gustaría pensar que es una mejor opción … Tenga en cuenta que la complejidad es la misma, O (2 ^ n), pero los requisitos de memoria se reducen (¡suponiendo que el recolector de basura se comporte!;))

 /** * */ package org.mechaevil.util.Algorithms; import java.util.BitSet; import java.util.Iterator; import java.util.Set; import java.util.TreeSet; /** * @author st0le * */ public class PowerSet implements Iterator>,Iterable>{ private E[] arr = null; private BitSet bset = null; @SuppressWarnings("unchecked") public PowerSet(Set set) { arr = (E[])set.toArray(); bset = new BitSet(arr.length + 1); } @Override public boolean hasNext() { return !bset.get(arr.length); } @Override public Set next() { Set returnSet = new TreeSet(); for(int i = 0; i < arr.length; i++) { if(bset.get(i)) returnSet.add(arr[i]); } //increment bset for(int i = 0; i < bset.size(); i++) { if(!bset.get(i)) { bset.set(i); break; }else bset.clear(i); } return returnSet; } @Override public void remove() { throw new UnsupportedOperationException("Not Supported!"); } @Override public Iterator> iterator() { return this; } } 

Para llamarlo, usa este patrón:

  Set set = new TreeSet (); for(int i = 0; i < 5; i++) set.add((char) (i + 'A')); PowerSet pset = new PowerSet(set); for(Set s:pset) { System.out.println(s); } 

Es de mi Biblioteca Project Euler … 🙂

Si n <63, que es una suposición razonable ya que se quedaría sin memoria (a menos que se use una implementación de iterador) intentando construir el conjunto de poder de todos modos, esta es una forma más concisa de hacerlo. Las operaciones binarias son mucho más rápidas que Math.pow() y las matrices para máscaras, pero de alguna manera los usuarios de Java les tienen miedo …

 List list = new ArrayList(originalSet); int n = list.size(); Set> powerSet = new HashSet>(); for( long i = 0; i < (1 << n); i++) { Set element = new HashSet(); for( int j = 0; j < n; j++ ) if( (i >> j) % 2 == 1 ) element.add(list.get(j)); powerSet.add(element); } return powerSet; 

Aquí hay un tutorial que describe exactamente lo que quiere, incluido el código. Tiene razón en que la complejidad es O (2 ^ n).

Se me ocurrió otra solución basada en las ideas de @Harry He. Probablemente no sea el más elegante, pero aquí va según lo entiendo:

Tomemos el clásico ejemplo simple PowerSet de SP (S) = {{1}, {2}, {3}}. Sabemos que la fórmula para obtener el número de subconjuntos es 2 ^ n (7 + conjunto vacío). Para este ejemplo 2 ^ 3 = 8 subconjuntos.

Para encontrar cada subconjunto necesitamos convertir 0-7 decimal a representación binaria que se muestra en la siguiente tabla de conversión:

Tabla de conversión

Si recorremos la tabla fila por fila, cada fila dará como resultado un subconjunto y los valores de cada subconjunto provendrán de los bits habilitados.

Cada columna en la sección Valor del contenedor corresponde a la posición del índice en el conjunto de entrada original.

Aquí mi código:

 public class PowerSet { /** * @param args */ public static void main(String[] args) { PowerSet ps = new PowerSet(); Set set = new HashSet(); set.add(1); set.add(2); set.add(3); for (Set s : ps.powerSet(set)) { System.out.println(s); } } public Set> powerSet(Set originalSet) { // Original set size eg 3 int size = originalSet.size(); // Number of subsets 2^n, eg 2^3 = 8 int numberOfSubSets = (int) Math.pow(2, size); Set> sets = new HashSet>(); ArrayList originalList = new ArrayList(originalSet); for (int i = 0; i < numberOfSubSets; i++) { // Get binary representation of this index eg 010 = 2 for n = 3 String bin = getPaddedBinString(i, size); //Get sub-set Set set = getSet(bin, originalList)); sets.add(set); } return sets; } //Gets a sub-set based on the binary representation. Eg for 010 where n = 3 it will bring a new Set with value 2 private Set getSet(String bin, List origValues){ Set result = new HashSet(); for(int i = bin.length()-1; i >= 0; i--){ //Only get sub-sets where bool flag is on if(bin.charAt(i) == '1'){ int val = origValues.get(i); result.add(val); } } return result; } //Converts an int to Bin and adds left padding to zero's based on size private String getPaddedBinString(int i, int size) { String bin = Integer.toBinaryString(i); bin = String.format("%0" + size + "d", Integer.parseInt(bin)); return bin; } } 

Si está utilizando colecciones Eclipse (anteriormente colecciones GS ), puede usar el método powerSet() en todos los SetIterables.

 MutableSet set = UnifiedSet.newSetWith(1, 2, 3); System.out.println("powerSet = " + set.powerSet()); // prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

Nota: soy un committer para las colecciones de Eclipse.

Estaba buscando una solución que no fuera tan grande como las que se publican aquí. Esto se dirige a Java 7, por lo que requerirá un puñado de pastas para las versiones 5 y 6.

 Set> powerSetofNodes(Set orig) { Set> powerSet = new HashSet<>(), runSet = new HashSet<>(), thisSet = new HashSet<>(); while (powerSet.size() < (Math.pow(2, orig.size())-1)) { if (powerSet.isEmpty()) { for (Object o : orig) { Set s = new TreeSet<>(); s.add(o); runSet.add(s); powerSet.add(s); } continue; } for (Object o : orig) { for (Set s : runSet) { Set s2 = new TreeSet<>(); s2.addAll(s); s2.add(o); powerSet.add(s2); thisSet.add(s2); } } runSet.clear(); runSet.addAll(thisSet); thisSet.clear(); } powerSet.add(new TreeSet()); return powerSet; 

Aquí hay un código de ejemplo para probar:

 Set hs = new HashSet<>(); hs.add(1); hs.add(2); hs.add(3); hs.add(4); for(Set s : powerSetofNodes(hs)) { System.out.println(Arrays.toString(s.toArray())); } 

La siguiente solución está tomada de mi libro ” Entrevistas de encoding: preguntas, análisis y soluciones “:

Se seleccionan algunos enteros en una matriz que componen una combinación. Se utiliza un conjunto de bits, donde cada bit representa un número entero en la matriz. Si el carácter i-ésimo se selecciona para una combinación, el bit i-ésimo es 1; de lo contrario, es 0. Por ejemplo, se usan tres bits para combinaciones de la matriz [1, 2, 3]. Si los dos primeros enteros 1 y 2 se seleccionan para componer una combinación [1, 2], los bits correspondientes son {1, 1, 0}. De manera similar, los bits correspondientes a otra combinación [1, 3] son ​​{1, 0, 1}. Podemos obtener todas las combinaciones de una matriz con longitud n si podemos obtener todas las combinaciones posibles de n bits.

Un número se compone de un conjunto de bits. Todas las combinaciones posibles de n bits corresponden a números de 1 a 2 ^ n -1. Por lo tanto, cada número en el rango entre 1 y 2 ^ n -1 corresponde a una combinación de una matriz con longitud n . Por ejemplo, el número 6 está compuesto por los bits {1, 1, 0}, por lo que los caracteres primero y segundo se seleccionan en el conjunto [1, 2, 3] para generar la combinación [1, 2]. De manera similar, el número 5 con los bits {1, 0, 1} corresponde a la combinación [1, 3].

El código de Java para implementar esta solución se ve a continuación:

 public static ArrayList> powerSet(int[] numbers) { ArrayList> combinations = new ArrayList>(); BitSet bits = new BitSet(numbers.length); do{ combinations.add(getCombination(numbers, bits)); }while(increment(bits, numbers.length)); return combinations; } private static boolean increment(BitSet bits, int length) { int index = length - 1; while(index >= 0 && bits.get(index)) { bits.clear(index); --index; } if(index < 0) return false; bits.set(index); return true; } private static ArrayList getCombination(int[] numbers, BitSet bits){ ArrayList combination = new ArrayList(); for(int i = 0; i < numbers.length; ++i) { if(bits.get(i)) combination.add(numbers[i]); } return combination; } 

El incremento del método aumenta un número representado en un conjunto de bits. El algoritmo borra 1 bit del bit del extremo derecho hasta que se encuentra un bit 0. A continuación, establece el bit 0 más a la derecha en 1. Por ejemplo, para boost el número 5 con los bits {1, 0, 1}, borra 1 bit del lado derecho y establece el bit 0 más a la derecha en 1. Los bits se convierten {1, 1, 0} para el número 6, que es el resultado de boost 5 por 1.

Algunas de las soluciones anteriores sufren cuando el tamaño del conjunto es grande porque están creando una gran cantidad de basura de objetos para ser recolectados y requieren copiar datos. ¿Cómo podemos evitar eso? Podemos aprovechar el hecho de que sabemos cuán grande será el tamaño del conjunto de resultados (2 ^ n), preasignar un conjunto tan grande y solo anexar al final del mismo, sin copiar nunca.

La aceleración crece rápidamente con n. Lo comparé con la solución anterior de João Silva. En mi máquina (todas las medidas son aproximadas), n = 13 es 5 veces más rápido, n = 14 es 7x, n = 15 es 12x, n = 16 es 25x, n = 17 es 75x, n = 18 es 140x. De modo que la creación / recolección y copia de basura está dominando en lo que de otro modo parecerían ser soluciones de gran O similares.

La asignación previa de la matriz al comienzo parece ser una victoria en comparación con dejarla crecer dinámicamente. Con n = 18, el crecimiento dynamic lleva aproximadamente el doble de tiempo en general.

 public static  List> powerSet(List originalSet) { // result size will be 2^n, where n=size(originalset) // good to initialize the array size to avoid dynamic growing int resultSize = (int) Math.pow(2, originalSet.size()); // resultPowerSet is what we will return List> resultPowerSet = new ArrayList>(resultSize); // Initialize result with the empty set, which powersets contain by definition resultPowerSet.add(new ArrayList(0)); // for every item in the original list for (T itemFromOriginalSet : originalSet) { // iterate through the existing powerset result // loop through subset and append to the resultPowerset as we go // must remember size at the beginning, before we append new elements int startingResultSize = resultPowerSet.size(); for (int i=0; i oldSubset = resultPowerSet.get(i); // create a new element by adding a new item from the original list List newSubset = new ArrayList(oldSubset); newSubset.add(itemFromOriginalSet); // add this element to the result powerset (past startingResultSize) resultPowerSet.add(newSubset); } } return resultPowerSet; } 

Aquí hay una solución iterativa fácil O (2 ^ n):

 public static Set> powerSet(List intList){ Set> result = new HashSet(); result.add(new HashSet()); for (Integer i : intList){ Set> temp = new HashSet(); for(Set intSet : result){ intSet = new HashSet(intSet); intSet.add(i); temp.add(intSet); } result.addAll(temp); } return result; } 
 import java.util.Set; import com.google.common.collect.*; Set> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3)); 

Si S es un conjunto finito con N elementos, entonces el conjunto de potencia de S contiene 2 ^ N elementos. El tiempo para simplemente enumerar los elementos del conjunto de poder es 2 ^ N, entonces O(2^N) es un límite inferior en la complejidad de tiempo (con entusiasmo) construyendo el conjunto de poder.

En pocas palabras, cualquier cálculo que implique la creación de grupos electrógenos no va a escalar para valores grandes de N. Ningún algoritmo inteligente lo ayudará … ¡además de evitar la necesidad de crear conjuntos de potencia!

Una forma sin recurrencia es la siguiente: use una máscara binaria y haga todas las combinaciones posibles.

 public HashSet createPowerSet(Object[] array) { HashSet powerSet=new HashSet(); boolean[] mask= new boolean[array.length]; for(int i=0;i 

Algoritmo:

Entrada: Set [], set_size 1. Obtenga el tamaño de la potencia set powet_set_size = pow (2, set_size) 2 Loop para contador de 0 a pow_set_size (a) Loop para i = 0 a set_size (i) Si ith bit in counter es establecer el elemento de impresión ith del conjunto para este subconjunto (b) Separador de impresión para subconjuntos, es decir, nueva línea

 #include  #include  void printPowerSet(char *set, int set_size) { /*set_size of power set of a set with set_size n is (2**n -1)*/ unsigned int pow_set_size = pow(2, set_size); int counter, j; /*Run from counter 000..0 to 111..1*/ for(counter = 0; counter < pow_set_size; counter++) { for(j = 0; j < set_size; j++) { /* Check if jth bit in the counter is set If set then pront jth element from set */ if(counter & (1< 

Esta es mi solución recursiva que puede obtener el poder de cualquier conjunto utilizando Java Generics. Su idea principal es combinar el cabezal de la matriz de entrada con todas las soluciones posibles del rest de la matriz de la siguiente manera.

 import java.util.LinkedHashSet; import java.util.Set; public class SetUtil { private static Set> combine(T head, Set> set) { Set> all = new LinkedHashSet<>(); for (Set currentSet : set) { Set outputSet = new LinkedHashSet<>(); outputSet.add(head); outputSet.addAll(currentSet); all.add(outputSet); } all.addAll(set); return all; } //Assuming that T[] is an array with no repeated elements ... public static Set> powerSet(T[] input) { if (input.length == 0) { Set >emptySet = new LinkedHashSet<>(); emptySet.add(new LinkedHashSet()); return emptySet; } T head = input[0]; T[] newInputSet = (T[]) new Object[input.length - 1]; for (int i = 1; i < input.length; ++i) { newInputSet[i - 1] = input[i]; } Set> all = combine(head, powerSet(newInputSet)); return all; } public static void main(String[] args) { Set> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6}); System.out.println(set); } } 

Esto dará como resultado:

 [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []] 

Este es mi enfoque con lambdas.

 public static  Set> powerSet(T[] set) { return IntStream .range(0, (int) Math.pow(2, set.length)) .parallel() //performance improvement .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet())) .map(Function.identity()) .collect(Collectors.toSet()); } 

O en paralelo (ver el comentario paralelo ()):

Tamaño del conjunto de entrada: 18

Procesadores lógicos: 8 a 3.4GHz

Mejora del rendimiento: 30%

Un subconjunto de t es cualquier conjunto que se puede hacer eliminando cero o más elementos de t. El subconjunto sin primer agrega los subconjuntos de t que faltan al primer elemento y el ciclo for se ocupará de agregar subconjuntos con el primer elemento. Por ejemplo, si t contenía los elementos [“1”, “2”, “3”], missingFirst agregará [[“”], [“2”], [“3”], [“2”, “3 “]] y el bucle for pegará el” 1 “al frente de estos elementos y lo agregará al newSet. Así que terminaremos con [[“”], [“1”], [“2”], [“3”], [“1”, “2”], [“1”, “3”] , [“2”, “3”], [“1”, “2”, “3”]].

 public static Set> allSubsets(Set t) { Set> powerSet = new TreeSet<>(); if(t.isEmpty()) { powerSet.add(new TreeSet<>()); return powerSet; } String first = t.get(0); Set> withoutFirst = allSubsets(t.subSet(1, t.size())); for (List 1st : withoutFirst) { Set newSet = new TreeSet<>(); newSet.add(first); newSet.addAll(lst); powerSet.add(newSet); } powerSet.addAll(withoutFirst); return powerSet; } 
 // input: S // output: P // S = [1,2] // P = [], [1], [2], [1,2] public static void main(String[] args) { String input = args[0]; String[] S = input.split(","); String[] P = getPowerSet(S); if (P.length == Math.pow(2, S.length)) { for (String s : P) { System.out.print("[" + s + "],"); } } else { System.out.println("Results are incorrect"); } } private static String[] getPowerSet(String[] s) { if (s.length == 1) { return new String[] { "", s[0] }; } else { String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length)); String[] subP2 = new String[subP1.length]; for (int i = 0; i < subP1.length; i++) { subP2[i] = s[0] + subP1[i]; } String[] P = new String[subP1.length + subP2.length]; System.arraycopy(subP1, 0, P, 0, subP1.length); System.arraycopy(subP2, 0, P, subP1.length, subP2.length); return P; } } 

Recientemente tuve que usar algo como esto, pero necesitaba las sublistas más pequeñas (con 1 elemento, luego 2 elementos, …) primero. No quería incluir la lista vacía ni toda la lista. Además, no necesitaba una lista de todas las sublistas devueltas, solo necesitaba hacer algunas cosas con cada una.

Quería hacer esto sin recurrencia, y se le ocurrió lo siguiente (con el “hacer cosas” abstraído en una interfaz funcional):

 @FunctionalInterface interface ListHandler { void handle(List list); } public static  void forAllSubLists(final List list, ListHandler handler) { int ll = list.size(); // Length of original list int ci[] = new int[ll]; // Array for list indices List sub = new ArrayList<>(ll); // The sublist List uml = Collections.unmodifiableList(sub); // For passing to handler for (int gl = 1, gm; gl <= ll; gl++) { // Subgroup length 1 .. n-1 gm = 0; ci[0] = -1; sub.add(null); // Some inits, and ensure sublist is at least gl items long do { ci[gm]++; // Get the next item for this member if (ci[gm] > ll - gl + gm) { // Exhausted all possibilities for this position gm--; continue; // Continue with the next value for the previous member } sub.set(gm, list.get(ci[gm])); // Set the corresponding member in the sublist if (gm == gl - 1) { // Ok, a sublist with length gl handler.handle(uml); // Handle it } else { ci[gm + 1] = ci[gm]; // Starting value for next member is this gm++; // Continue with the next member } } while (gm >= 0); // Finished cycling through all possibilities } // Next subgroup length } 

De esta forma, también es fácil limitarlo a sublistas de longitudes específicas.

Otra implementación de muestra:

  public static void main(String args[]) { int[] arr = new int[]{1,2,3,4}; // Assuming that number of sets are in integer range int totalSets = (int)Math.pow(2,arr.length); for(int i=0;i 
 public class PowerSet { public static List> powerset(int[] a) { LinkedList> sets = new LinkedList>(); int n = a.length; for (int i = 0; i < 1 << n; i++) { HashSet set = new HashSet(); for (int j = 0; j < n; j++) { if ((1 << j & i) > 0) set.add(a[j]); } sets.add(set); } return sets; } public static void main(String[] args) { List> sets = PowerSet.powerset(new int[]{ 1, 2, 3 }); for (HashSet set : sets) { for (int i : set) System.out.print(i); System.out.println(); } } } 

Otra solución más: con java8 + streaming api. Es floja y ordenada, por lo que devuelve los subconjuntos correctos cuando se usa con “limit ()”.

  public long bitRangeMin(int size, int bitCount){ BitSet bs = new BitSet(size); bs.set(0, bitCount); return bs.toLongArray()[0]; } public long bitRangeMax(int size, int bitCount){ BitSet bs = BitSet.valueOf(new long[]{0}); bs.set(size - bitCount, size); return bs.toLongArray()[0]; } public  Stream> powerSet(Collection data) { List list = new LinkedHashSet<>(data).stream().collect(Collectors.toList()); Stream head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i})); Stream tail = IntStream.rangeClosed(1, list.size()) .boxed() .flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1)) .mapToObj(v2 -> BitSet.valueOf(new long[]{v2})) .filter( bs -> bs.cardinality() == v1)); return Stream.concat(head, tail) .map( bs -> bs .stream() .mapToObj(list::get) .collect(Collectors.toList())); } 

Y el código del cliente es

 @Test public void testPowerSetOfGivenCollection(){ List data = new LinkedList<>(); for(char i = 'a'; i < 'a'+5; i++ ){ data.add(i); } powerSet(data) .limit(9) .forEach(System.out::print); } 

/ * Imprime: [] [a] [b] [c] [d] [e] [a, b] [a, c] [b, c] * /

Podríamos escribir la potencia establecida con o sin el uso de recursividad. Aquí hay un bash sin recurrencia:

 public List> getPowerSet(List set) { List> powerSet = new ArrayList>(); int max = 1 << set.size(); for(int i=0; i < max; i++) { List subSet = getSubSet(i, set); powerSet.add(subSet); } return powerSet; } private List getSubSet(int p, List set) { List subSet = new ArrayList(); int position = 0; for(int i=p; i > 0; i >>= 1) { if((i & 1) == 1) { subSet.add(set.get(position)); } position++; } return subSet; } 

Aquí está para generar un conjunto de potencia. La idea es primero = S[0] y los conjuntos más pequeños son S[1,...n] .

Calcule todos los subconjuntos de smallerSet y colóquelos en allsubsets.

Para cada subconjunto en todos los subconjuntos, clonar y agregar primero al subconjunto.

 ArrayList> getSubsets(ArrayList set, int index){ ArrayList> allsubsets; if(set.size() == index){ allsubsets = new ArrayList>(); allsubsets.add(new ArrayList()); // the empty set }else{ allsubsets = getSubsets(set, index+1); int item = set.get(index); ArrayList> moresubsets = new ArrayList>(); for(ArrayList subset: allsubsets){ ArrayList newsubset = new ArrayList(); newsubset.addAll(subset); newsubset.add(item); moresubsets.add(newsubset); } moresubsets.addAll(moresubsets); } return allsubsets; }