Que algoritmo devo usar?

Assuntos Gerais
#1

Aew galera, tô desenvolvendo uma classe Conjunto em Java e preciso de um metodo que realize a operacao de conjunto das partes de um conjunto( esta operação retorna o conjunto de todos os subconjuntos do conjunto original ). Ja tentei fazer iterativo e recursivo mas não tive sucesso. Se alguem souber como se implementa Conjunto Das Partes de um conjunto ou souber de algum site que tem um pseudo-codigo, ideia, ou implementação, eu agradeceria muito pela ajuda.

Desde já agradeço.

Leandro Max

#2

Olá

Conjuntos existem em Java como HashSet ou TreeSet. Se quiser algo especial extenda e implemente o que já existe pronto.

java.util.AbstractCollection
|_ java.util.AbstractSet

Para o seu caso veja o método public boolean retainAll(Collection c) de AbstractCollection.

[]s
Luca

#3

[quote=“Luca”]Olá

Conjuntos existem em Java como HashSet ou TreeSet. Se quiser algo especial extenda e implemente o que já existe pronto.

java.util.AbstractCollection
|_ java.util.AbstractSet

Para o seu caso veja o método public boolean retainAll(Collection c) de AbstractCollection.

[]s
Luca[/quote]

Oi, creio que este metodo, retainAll( Collection c ) não serve para o meu caso, este metodo eu usei para fazer interseção de conjuntos( eh muito adequado ), mas eu tô interessado mesmo eh no algoritmo, a ideia de como achar todos os subconjuntos de um conjunto.

Obrigado.

#4

Voce pode implementar da seguinte forma:

//Retorna todos subconjuntos de cardinalidade n - 1
Collection subconjuntosM1(Set conjunto) {
  Collection res = new ArrayList();
  for(int i = 0; i < conjunto.size(); ++i)
    res.add(conjunto.clone());

  for(Iterator i = conjunto.iterator(), j = res.iterator(); i.hasNext(); ) {
    ((Collection)j.next()).remove(i.next());
  }
  return res;
}

Collection todosSubConjuntos(Set conjunto) {
    if(conjunto.size() == 1)
      return Collections.singletonSet(conjunto);

  Collection res = new ArrayList();
  Collection sub = subconjuntosM1(conjunto);
  for(Iterator i = sub.iterator(); i.hasNext(); ) 
    res.putAll(todosSubConjuntos((Set)i.next());
 
   return res;
}

Não testei, mas deve te dar 1 boa idéia de como fazer.

Dado o conjunto N de cardinalidade n gere todos os n subconjuntos de cardinalidade n-1. Só repetir esse processo recursivamente e para quando encontrar conjuntos unitarios.
Para gerar os n subconjuntos: crie n copias de N, então remova de cada copia um elemento distinto de N.

#5

ola!

eu tive o seguinte problema na faculdade semestre passado:

o seu problema seria mais ou menos isso? se for, eu publiquei uma “quase-solucao” do problema no meu site… a solucao do problema dá todos os subconjuntos, o problema é q nao está em ordem lexicografica (se vc descobrir como fazer isso me fale - sem passar por um algoritmo de ordenacao, logico!)

bom, o link é:

http://www.tatanka.com.br/bcc/MAC122/lista3/Ex13.java

se for util em alguma coisa, de um retorno…

#6

sergio, sua versao esta array oriented :)…

entao, o nome disso ai eh POWERSET, o do louds e do sergio tao certinhos

#7

Pode também ser uma sequencia.

#8

[quote=“Paulo Silveira”]sergio, sua versao esta array oriented :)…

entao, o nome disso ai eh POWERSET, o do louds e do sergio tao certinhos[/quote]

sim… e o codigo ta zuado tbm (nem um pouco Java…heheheh)
mas, como o jmaster tava procurando um algoritmo, talvez a ideia do algoritmo ajude… ele mostra como pode usar recursao para resolver o problema

#9

Valew galera, eu estava agora estudando um algoritmo que resolve o problema, mas ele eh iterativo e seu codigo ( em C ) está muito obscuro. Estes em java são bem mais simples para assimilar a ideia.

Obrigado

#10