Calcolo di tutti i sottoinsiemi di un insieme di numeri

Voglio trovare i sottoinsiemi di un insieme di numeri interi. È il primo passo dell’algoritmo “Sum of Subsets” con backtracking. Ho scritto il seguente codice, ma non restituisce la risposta corretta:

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; } 

Ad esempio, se voglio calcolare i sottoinsiemi di set = {1, 3, 5} Il risultato del mio metodo è:

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

Voglio che produca:

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

Penso che il problema sia dalla lista list.removeAll (lista); ma non so come correggerlo.

Quello che vuoi è chiamato Powerset . Ecco una semplice implementazione di questo:

 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; } 

Ti darò un esempio per spiegare come funziona l’algoritmo per il powerset di {1, 2, 3} :

  • Rimuovi {1} ed esegui powerset per {2, 3} ;
    • Rimuovi {2} ed esegui powerset per {3} ;
      • Rimuovi {3} ed esegui powerset per {} ;
        • Il Potere di {} è {{}} ;
      • Il Powerset di {3} è 3 combinato con {{}} = { {}, {3} } ;
    • Powerset di {2, 3} è {2} combinato con { {}, {3} } = { {}, {3}, {2}, {2, 3} } ;
  • Il Powerset di {1, 2, 3} è {1} combinato con { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} } .

Solo un primer come potresti risolvere il problema:

Approccio 1

  • Prendi il primo elemento della tua lista di numeri
  • genera tutti i sottoinsiemi dalla lista dei numeri rimanenti (cioè la lista dei numeri senza quella scelta) => Ricorsione!
  • per ogni sottoinsieme trovato nel passaggio precedente, aggiungi il sottoinsieme stesso e il sottoinsieme unito con l’elemento scelto nel passaggio 1 all’output.

Certo, devi controllare il caso base, cioè se la tua lista numerica è vuota.

Approccio 2

È noto che un set con n elementi ha 2^n sottoinsiemi. Quindi, puoi contare in binario da 0 a 2^n e interpretare il numero binario come sottoinsieme corrispondente. Si noti che questo approccio richiede un numero binario con una quantità sufficiente di cifre per rappresentare l’intero set.

Dovrebbe essere un problema non troppo grande per convertire uno dei due approcci in codice.

Il tuo codice è davvero confuso e non c’è alcuna spiegazione.

Puoi fare iterativamente con una maschera di bit che determina quali numeri sono nel set. Ad esempio, ogni numero da 0 a 2 ^ n fornisce un sottoinsieme unico nella sua rappresentazione binaria

per n = 3:

i = 5 -> 101 in binario, scegli il primo e l’ultimo elemento i = 7 -> 111 in binario, scegli i primi 3 elementi

Supponiamo che ci siano n elementi (n <64, dopotutto se n è maggiore di 64 lo eseguirai per sempre).

 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 } 

Considerando un visitatore Noob (grazie a google) a questa domanda – come me
Ecco una soluzione ricorsiva che funziona sul principio semplice:

Set = {a, b, c, d, e}
quindi possiamo suddividerlo in {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 

PRODUZIONE

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

È chiaro che il numero totale di sottoinsiemi di un dato insieme è uguale a 2 ^ (numero di elementi nell’insieme). Se impostato

A = {1, 2, 3}

quindi il sottoinsieme di A è:

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

Se guardiamo è come numeri binari.

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

Se prendiamo in considerazione sopra:

 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("}"); } } 

Sulla base di ciò che ho imparato oggi, ecco la soluzione Java. Si basa sulla 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; } } 

Eseguirlo darà risultati come

 [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] 

Stavo davvero cercando di risolvere questo e ho ottenuto l’algoritmo @phimuemue nel post precedente. Ecco cosa ho implementato. Spero che funzioni.

 /** *@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; } 

Ecco alcuni pseudocodici. È ansible tagliare le stesse chiamate ricorsive memorizzando i valori per ciascuna chiamata man mano che si procede e prima di verificare la chiamata ricorsiva se il valore della chiamata è già presente.

Il seguente algoritmo avrà tutti i sottoinsiemi escludendo il set vuoto.

 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 

Se hai a che fare con una vasta raccolta di elementi, potresti (anche se non probabile) incorrere in problemi con lo stack overflow. Ammetto che è più probabile che si esaurisca la memoria prima di sovraccaricare lo stack, ma in ogni caso metterò questo metodo non ricorsivo.

 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 se preferisci occuparti di array:

 @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; }