Arquivo Discussoes de Programacao e Tecnologia 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
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
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.AbstractSetPara o seu caso veja o método public boolean retainAll(Collection c) de AbstractCollection.
[]s
Luca
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.
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.
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…
sergio, sua versao esta array oriented :)…
entao, o nome disso ai eh POWERSET, o do louds e do sergio tao certinhos
Pode também ser uma sequencia.
sergio, sua versao esta array oriented :)…entao, o nome disso ai eh POWERSET, o do louds e do sergio tao certinhos
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
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