Olá! Achei estranho pois fiz uma pesquisa rápida e não achei nada sobre o assunto (ou não pesquisei direito, sei lá).
O problema é o seguinte: tenho por exemplo um arranjo com {A,B,C} e tenho que retornar todas as combinações possíveis com um tamanho x sem repetir os termos. Nesse caso retornaria {A, B, C, AB, AC, BC, ABC}. Só encontro algoritmos que retornam o número de combinações, e não quais são exatamente. Nesse caso tem que ser um algoritmo recursivo, certo? Alguém conhece algum ou tem idéia de como fazer? Obrigada.
[RESOLVIDO] Combinação sem repetição
5 Respostas
Oi,
dá uma olhadinha aqui, no final tem o código em java.
mas esse aí retorna com repetição!
pra mim AB e BA seria a mesma coisa(teria que retornar apenas um deles), pois estou mexendo com estados de um autômato finito não determinístico.
L
Bom dia!
Não vi o código do orobsonpires porque o link não abriu para mim.
Fiz o código abaixo, que não deve ser o mais performante, mas funcionou... O principal é testar se já existe a combinação antes de inserir na lista!
A lista de objetos/estados pode ser qualquer coisa que implemente Comparable. Isso só para poder ordenar "bonitinho" a saída no final.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
public class Comb {
/**
* @param args
*/
public static void main(String[] args) {
String[] status = new String[] { "A", "B", "C", "D" }; //aqui pode ser qualquer objeto que implemente Comparable
List<SortedSet<Comparable>> allCombList = new ArrayList<SortedSet<Comparable>>(); //aqui vai ficar a resposta
for (String nstatus : status) {
allCombList.add(new TreeSet<Comparable>(Arrays.asList(nstatus))); //insiro a combinação "1 a 1" de cada item
}
for (int nivel = 1; nivel < status.length; nivel++) {
List<SortedSet<Comparable>> statusAntes = new ArrayList<SortedSet<Comparable>>(allCombList); //crio uma cópia para poder não iterar sobre o que já foi
for (Set<Comparable> antes : statusAntes) {
SortedSet<Comparable> novo = new TreeSet<Comparable>(antes); //para manter ordenado os objetos dentro do set
novo.add(status[nivel]);
if (!allCombList.contains(novo)) { //testo para ver se não está repetido
allCombList.add(novo);
}
}
}
Collections.sort(allCombList, new Comparator<SortedSet<Comparable>>() { //aqui só para organizar a saída de modo "bonitinho"
@Override
public int compare(SortedSet<Comparable> o1, SortedSet<Comparable> o2) {
int sizeComp = o1.size() - o2.size();
if (sizeComp == 0) {
Iterator<Comparable> o1iIterator = o1.iterator();
Iterator<Comparable> o2iIterator = o2.iterator();
while (sizeComp == 0 && o1iIterator.hasNext() ) {
sizeComp = o1iIterator.next().compareTo(o2iIterator.next());
}
}
return sizeComp;
}
});
System.out.println(allCombList);
}
}
Resposta:
[[A], [B], [C], [D], [A, B], [A, C], [A, D], [B, C], [B, D], [C, D], [A, B, C], [A, B, D], [A, C, D], [B, C, D], [A, B, C, D]]
Um outro jeito é "deixar a lista ordenada e única" com um SortedSet... A verificação se já não existe é feita "por baixo" pelo SortedSet. Então, o 'for' fica mais limpo!
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
public class Comb {
/**
* @param args
*/
public static void main(String[] args) {
String[] status = new String[] { "A", "B", "C", "D" };
SortedSet<SortedSet<Comparable>> allCombList = new TreeSet<SortedSet<Comparable>>(new Comparator<SortedSet<Comparable>>() {
@Override
public int compare(SortedSet<Comparable> o1, SortedSet<Comparable> o2) {
int sizeComp = o1.size() - o2.size();
if (sizeComp == 0) {
Iterator<Comparable> o1iIterator = o1.iterator();
Iterator<Comparable> o2iIterator = o2.iterator();
while (sizeComp == 0 && o1iIterator.hasNext() ) {
sizeComp = o1iIterator.next().compareTo(o2iIterator.next());
}
}
return sizeComp;
}
});
for (String nstatus : status) {
allCombList.add(new TreeSet<Comparable>(Arrays.asList(nstatus)));
}
for (int nivel = 1; nivel < status.length; nivel++) {
List<SortedSet<Comparable>> statusAntes = new ArrayList<SortedSet<Comparable>>(allCombList);
for (Set<Comparable> antes : statusAntes) {
SortedSet<Comparable> novo = new TreeSet<Comparable>(antes);
novo.add(status[nivel]);
allCombList.add(novo);
}
}
System.out.println(allCombList);
}
}
Era bem oq precisava, muito obrigada!
L
:thumbup:
Agora só fechar o tópico colocando [RESOLVIDO] no primeiro post!
Criado 23 de maio de 2011
Ultima resposta 25 de mai. de 2011
Respostas 5
Participantes 3
Alura Sistemas operacionais: entenda seu conceito e suas funções Descubra o que são sistemas operacionais, suas funções e tipos. Aprenda tudo de forma clara e objetiva. Não perca tempo!
Casa do Codigo Orientacao a Objetos: Aprenda seus conceitos e suas... Por Thiago Leite e Carvalho — Casa do Codigo