Cálculo de todos los subconjuntos de un conjunto de números

Quiero encontrar los subconjuntos de un conjunto de enteros. Es el primer paso del algoritmo “Suma de subconjuntos” con retroceso. He escrito el siguiente código, pero no devuelve la respuesta correcta:

BTSum(0, nums); ///************** ArrayList list = new ArrayList(); public static ArrayList BTSum(int n, ArrayList numbers) { if (n == numbers.size()) { for (Integer integer : list) { System.out.print(integer+", "); } System.out.println("********************"); list.removeAll(list); System.out.println(); } else { for (int i = n; i < numbers.size(); i++) { if (i == numbers.size() - 1) { list.add(numbers.get(i)); BTSum(i + 1, numbers); } else { list.add(numbers.get(i)); for (int j = i+1; j < numbers.size(); j++) BTSum(j, numbers); } } } return null; } 

Por ejemplo, si quiero calcular los subconjuntos de set = {1, 3, 5} El resultado de mi método es:

  1, 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ******************** 3, 5, ******************** 5, ******************** 

Quiero que produzca:

 1, 3, 5 1, 5 3, 5 5 

Creo que el problema es de la lista de partes.removeTodo (lista); pero no sé cómo corregirlo

Lo que quieres se llama Powerset . Aquí hay una implementación simple de esto:

 public static Set> powerSet(Set originalSet) { Set> sets = new HashSet>(); if (originalSet.isEmpty()) { sets.add(new HashSet()); return sets; } List list = new ArrayList(originalSet); Integer 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; } 

Le daré un ejemplo para explicar cómo funciona el algoritmo para el conjunto de poder de {1, 2, 3} :

  • Quite {1} y ejecute powerset para {2, 3} ;
    • Quite {2} y ejecute powerset para {3} ;
      • Quite {3} y ejecute powerset para {} ;
        • Powerset de {} es {{}} ;
      • Powerset de {3} es 3 combinado con {{}} = { {}, {3} } ;
    • Powerset de {2, 3} es {2} combinado con { {}, {3} } = { {}, {3}, {2}, {2, 3} } ;
  • Powerset de {1, 2, 3} es {1} combinado con { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} } .

Solo una introducción sobre cómo podrías resolver el problema:

Enfoque 1

  • Tome el primer elemento de su lista de números
  • generar todos los subconjuntos de la lista de números restantes (es decir, la lista de números sin la elegida) => Recursión!
  • para cada subconjunto encontrado en el paso anterior, agregue el subconjunto mismo y el subconjunto unido con el elemento elegido en el paso 1 a la salida.

Por supuesto, debe verificar el caso base, es decir, si su lista de números está vacía.

Enfoque 2

Es un hecho bien conocido que un conjunto con n elementos tiene 2^n subconjuntos. Por lo tanto, puede contar en binario de 0 a 2^n e interpretar el número binario como el subconjunto correspondiente. Tenga en cuenta que este enfoque requiere un número binario con una cantidad suficiente de dígitos para representar todo el conjunto.

No debería ser un problema demasiado grande convertir uno de los dos enfoques en código.

Tu código es realmente confuso y no hay explicación.

Puedes hacer iterativamente con una máscara de bits que determina qué números están en el conjunto. Cada número de 0 a 2 ^ n da un subconjunto único en su representación binaria, por ejemplo

para n = 3:

i = 5 -> 101 en binario, elija el primer y último elemento i = 7 -> 111 en binario, elija los primeros 3 elementos

Supongamos que hay n elementos (n <64, después de todo, si n es mayor que 64, lo ejecutará para siempre).

 for(long i = 0; i < (1< subset = new ArrayList(); for(int j = 0; j < n; j++){ if((i>>j) & 1) == 1){ // bit j is on subset.add(numbers.get(j)); } } // print subset } 

Considerar a un visitante novato (gracias a google) a esta pregunta, como yo
Aquí hay una solución recursiva que funciona en principio simple:

Set = {a, b, c, d, e}
entonces podemos dividirlo en {a} + Subset of {b,c,d,e}

 public class Powerset{ String str = "abcd"; //our string public static void main(String []args){ Powerset ps = new Powerset(); for(int i = 0; i< ps.str.length();i++){ //traverse through all characters ps.subs("",i); } } void subs(String substr,int index) { String s = ""+str.charAt(index); //very important, create a variable on each stack s = substr+s; //append the subset so far System.out.println(s); //print for(int i=index+1;i 

SALIDA

 a ab abc abcd abd ac acd ad b bc bcd bd c cd d 

Está claro que, el número total de subconjuntos de cualquier conjunto dado es igual a 2 ^ (número de elementos en el conjunto). Si se establece

A = {1, 2, 3}

entonces el subconjunto de A es:

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

Si lo vemos, es como números binarios.

{000}, {001}, {010}, {011}, {100}, {101}, {110}, {111}

Si tomamos en cuenta arriba:

 static void subSet(char[] set) { int c = set.length; for (int i = 0; i < (1 << c); i++) { System.out.print("{"); for (int j = 0; j < c; j++) { if ((i & (1 << j)) > 0) { System.out.print(set[j] + " "); } } System.out.println("}"); } } public static void main(String[] args) { char c[] = {'a', 'b', 'c'}; subSet(c); } 
 private static void findSubsets(int array[]) { int numOfSubsets = 1 << array.length; for(int i = 0; i < numOfSubsets; i++) { int pos = array.length - 1; int bitmask = i; System.out.print("{"); while(bitmask > 0) { if((bitmask & 1) == 1) System.out.print(array[pos]+","); bitmask >>= 1; pos--; } System.out.print("}"); } } 

De acuerdo con lo que aprendí hoy, aquí está la solución de Java Se basa en la recursion

 public class Powerset { public static void main(String[] args) { final List> allSubsets = powerSet(Arrays.asList(1, 2, 3, 4), 0); for (List subsets : allSubsets) { System.out.println(subsets); } } private static List> powerSet(final List values, int index) { if (index == values.size()) { return new ArrayList<>(); } int val = values.get(index); List> subset = powerSet(values, index + 1); List> returnList = new ArrayList<>(); returnList.add(Arrays.asList(String.valueOf(val))); returnList.addAll(subset); for (final List subsetValues : subset) { for (final String subsetValue : subsetValues) { returnList.add(Arrays.asList(val + "," + subsetValue)); } } return returnList; } } 

Ejecutarlo dará resultados como

 [1] [2] [3] [4] [3,4] [2,3] [2,4] [2,3,4] [1,2] [1,3] [1,4] [1,3,4] [1,2,3] [1,2,4] [1,2,3,4] 

En realidad, estaba tratando de resolver este problema y obtuve el algoritmo @phimuemue en la publicación anterior. Aquí es lo que implementé. Espero que esto funcione.

 /** *@Sherin Syriac * */ import java.util.ArrayList; import java.util.List; public class SubSet { ArrayList> allSubset = new ArrayList>(); /** * @param args */ public static void main(String[] args) { SubSet subSet = new SubSet(); ArrayList set = new ArrayList(); set.add(1); set.add(2); set.add(3); set.add(4); subSet.getSubSet(set, 0); for (List list : subSet.allSubset) { System.out.print("{"); for (Integer element : list) { System.out.print(element); } System.out.println("}"); } } public void getSubSet(ArrayList set, int index) { if (set.size() == index) { ArrayList temp = new ArrayList(); allSubset.add(temp); } else { getSubSet(set, index + 1); ArrayList> tempAllSubsets = new ArrayList>(); for (List subset : allSubset) { ArrayList newList = new ArrayList(); newList.addAll(subset); newList.add(set.get(index)); tempAllSubsets.add(newList); } allSubset.addAll(tempAllSubsets); } } } 
 // subsets for the set of 5,9,8 import java.util.ArrayList; import java.util.List; public class Subset { public static void main(String[] args) { List s = new ArrayList(); s.add(9); s.add(5); s.add(8); int setSize = s.size(); int finalValue = (int) (Math.pow(2, setSize)); String bValue = ""; for (int i = 0; i < finalValue; i++) { bValue = Integer.toBinaryString(i); int bValueSize = bValue.length(); for (int k = 0; k < (setSize - bValueSize); k++) { bValue = "0" + bValue; } System.out.print("{ "); for (int j = 0; j < setSize; j++) { if (bValue.charAt(j) == '1') { System.out.print((s.get(j)) + " "); } } System.out.print("} "); } } } //Output : { } { 8 } { 5 } { 5 8 } { 9 } { 9 8 } { 9 5 } { 9 5 8 } 
 public static ArrayList> powerSet(List intList) { ArrayList> result = new ArrayList>(); result.add(new ArrayList()); for (int i : intList) { ArrayList> temp = new ArrayList>(); for (ArrayList innerList : result) { innerList = new ArrayList(innerList); innerList.add(i); temp.add(innerList); } result.addAll(temp); } return result; } 

Aquí hay un pseudocódigo. Puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada sobre la marcha y antes de la comprobación recursiva de llamadas si el valor de la llamada ya está presente.

El siguiente algoritmo tendrá todos los subconjuntos excluyendo el conjunto vacío.

 list * subsets(string s, list * v){ if(s.length() == 1){ list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i 

Si está tratando con una gran colección de elementos, es posible (aunque no probable) que tenga problemas con el desbordamiento de la stack. Admito que es más probable que se quede sin memoria antes de desbordar la stack, pero de todos modos pondré este método no recursivo.

 public static final  Set> powerSet(final Iterable original) { Set> sets = new HashSet<>(); sets.add(new HashSet<>()); for (final T value : original) { final Set> newSets = new HashSet<>(sets); for (final Set set : sets) { final Set newSet = new HashSet<>(set); newSet.add(value); newSets.add(newSet); } sets = newSets; } return sets; } 

O si prefieres tratar con matrices:

 @SuppressWarnings("unchecked") public static final  T[][] powerSet(final T... original) { T[][] sets = (T[][]) Array.newInstance(original.getClass(), 1); sets[0] = Arrays.copyOf(original, 0); for (final T value : original) { final int oldLength = sets.length; sets = Arrays.copyOf(sets, oldLength * 2); for (int i = 0; i < oldLength; i++) { final T[] oldArray = sets[i]; final T[] newArray = Arrays.copyOf(oldArray, oldArray.length + 1); newArray[oldArray.length] = value; sets[i + oldLength] = newArray; } } return sets; }