Calculando todos os subconjuntos de um conjunto de números

Eu quero encontrar os subconjuntos de um conjunto de inteiros. É o primeiro passo do algoritmo “Soma dos Subconjuntos” com backtracking. Eu escrevi o seguinte código, mas ele não retorna a resposta correta:

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 exemplo, se eu quiser calcular os subconjuntos de set = {1, 3, 5} O resultado do meu método é:

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

Eu quero produzir:

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

Eu acho que o problema é da parte list.removeAll (list); mas eu não sei como corrigir isso.

O que você quer é chamado de Powerset . Aqui está uma simples implementação:

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

Vou dar um exemplo para explicar como o algoritmo funciona para o conjunto de {1, 2, 3} :

  • Remova {1} e execute o conjunto de comandos para {2, 3} ;
    • Remova {2} e execute o conjunto de comandos para {3} ;
      • Remova {3} e execute o conjunto de comandos para {} ;
        • Powerset de {} é {{}} ;
      • Powerset de {3} é 3 combinado com {{}} = { {}, {3} } ;
    • Powerset de {2, 3} é {2} combinado com { {}, {3} } = { {}, {3}, {2}, {2, 3} } ;
  • Powerset de {1, 2, 3} é {1} combinado com { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} } .

Apenas uma cartilha como você poderia resolver o problema:

Abordagem 1

  • Pegue o primeiro elemento da sua lista de números
  • gerar todos os subconjuntos da lista de números restantes (ou seja, a lista de números sem o escolhido) => Recursão!
  • para cada subconjunto encontrado na etapa anterior, inclua o subconjunto e o subconjunto associado ao elemento escolhido na etapa 1 na saída.

Claro, você tem que verificar o caso base, ou seja, se a sua lista de números está vazia.

Abordagem 2

É um fato bem conhecido que um conjunto com n elementos possui 2^n subconjuntos. Assim, você pode contar em binário de 0 a 2^n e interpretar o número binário como o subconjunto correspondente. Observe que essa abordagem exige um número binário com uma quantidade suficiente de dígitos para representar todo o conjunto.

Deve ser um problema não muito grande para converter uma das duas abordagens em código.

Seu código é realmente confuso e não há explicação.

Você pode fazer iterativamente com um bitmask que determina quais números estão no conjunto. Cada número de 0 a 2 ^ n fornece um subconjunto único em sua representação binária, por exemplo

para n = 3:

i = 5 -> 101 em binário, escolha primeiro e último elementos i = 7 -> 111 em binário, escolha os 3 primeiros elementos

Suponha que haja n elementos (n <64, afinal, se n for maior que 64, você executará isso para 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 um Visitante Noob (graças ao google) para esta questão – como eu
Aqui está uma solução recursiva que funciona no princípio simples:

Set = {a, b, c, d, e}
então podemos dividi-lo em {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 

SAÍDA

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

É claro que, o número total de subconjuntos de qualquer conjunto dado é igual a 2 ^ (número de elementos no conjunto). Se definido

A = {1, 2, 3}

então o subconjunto de A é:

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

Se olharmos, é como números binários.

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

Se levarmos em conta acima:

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

Com base no que aprendi hoje, aqui está a solução Java. Ela é baseada em 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; } } 

Correndo ele vai 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] 

Eu estava realmente tentando resolver este e tenho o algoritmo @phimuemue no post anterior. Aqui está o que eu implementei. Espero que isso 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; } 

Aqui está algum pseudocódigo. Você pode cortar as mesmas chamadas recursivas armazenando os valores de cada chamada durante a execução e antes da verificação de chamadas recursivas, se o valor da chamada já estiver presente.

O algoritmo a seguir terá todos os subconjuntos excluindo o conjunto vazio.

 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 você está lidando com uma grande coleção de elementos, você pode (embora não seja provável) ter problemas com o estouro de pilha. Eu admito que você está mais propenso a ficar sem memory antes de você sobrecarregar a pilha, mas eu vou colocar este método não-recursivo aqui de qualquer maneira.

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

Ou se preferir lidar com matrizes:

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