[RESOLVIDO] Combinação sem repetição

Programação Java
#1

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.

#2

Oi,

dá uma olhadinha aqui, no final tem o código em java.

#3

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.

#4

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.

[code]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);
}

}[/code]

Resposta:

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!

[code]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);
}

}[/code]

#5

Era bem oq precisava, muito obrigada!

#6

:thumbup:

Agora só fechar o tópico colocando [RESOLVIDO] no primeiro post!

#7