Pessoal,
To precisando de ajuda pra desenvolver um algoritmo de força bruta.
Seria mais ou menos assim, tenho um List contendo os objetos a,b,c e d
Preciso percorrer todos de todas as formas possiveis, mantendo sempre o a como primeiro elemento,
Ficaria assim
a b c d
a b d c
a c b d
a c d b
a d b c
a d c b
Mas não consigo pensar em uma forma de fazer isso.
Alguem poderia me indicar o caminho, por onde eu começo.
vlww
Bom dia amigo,
Não sei se seria o caso, mais poderia utilizar estruturas de repetição aninhadas, como por exemplo as que utilizamos para iterar arrays de muitas dimensões, como for dentro de for.
Espero ter ajudado. Abraços.
Procure por “gerar permutações em ordem lexicográfica”. Existem até métodos prontos em Java que fazem isso, basta procurar um pouco (procure por “permutations” e “lexicographical order”.)
Olha no meu repositório do github, tem uma classe que eu fiz uma vez pra fazer isso aí:
Dá uma lida no javadoc para ver como utilizar a classe.
Até mais!
Rogério, fiquei com preguiça de tentar entender o seu programa. Pelo que você disse no seu javadoc, ele gera as combinações, não as permutações.
Só me dê uma idéia: digamos que você passe a string “abc”.
Ele gera as 3 ^3 = 27 combinações (aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, … ccc) ou ele gera as 3! = 6 permutações (abc, acb, … cba) ?
É que o marcos4ft aparentemente quer as permutações, não as combinações.
Ele vai gerar todas as combinações possíveis, como no exemplo do javadoc:
import static GeradorPalavras.*;
...
public static void main(String[] args) {
final StringBuilder strBuilder = new StringBuilder();
String ascii = "ab";
ProcessadorPalavra ex = new ProcessadorPalavra() {
public void processarPalavra( String palavra, long contPalavraAtual, long totalPalavras ) {
strBuilder.delete(0, strBuilder.length())
.append(contPalavraAtual+1).append("/").append(totalPalavras)
.append(" --> ").append(palavra);
System.out.println(strBuilder.toString());
}
};
gerarPalavras(ascii, 4, ex);
}No caso acima, ele vai gerar todas as combinações possíveis das letras a e b e imprimir no console. Eu não sei se serve para o caso dele, mas acho que deve dar uma idéia de como pode ser implementado. Eu achei que eram as combinações possíveis pois ele disse sobre algoritmo de força bruta e normalmente neste caso são geradas as combinações possíveis, mas pode ser que eu tenha entendido errado o que ele quer.
Então são as combinações, não as permutações. Certo.
De qualquer forma, se for necessário ter as permutações (não as combinações), fica a dica para ele procurar um pouquinho pelas palavras-chave que passei.
Pelo que eu entendi, as permutações estão também dentro das combinações possíveis, então poderíamos utilizar o mesmo algoritmo, só que eliminando os casos que
algum dos elementos se repetem. Eu escrevi uma outra implementação da interface que ignora os casos repetidos e imprime apenas os que não se repetem:
public static void main(String[] args) {
final StringBuilder strBuilder = new StringBuilder();
final String ascii = "abc";
final char[] array = ascii.toCharArray();
ProcessadorPalavra ex = new ProcessadorPalavra() {
public void processarPalavra(String palavra, long contPalavraAtual,
long totalPalavras) {
boolean ignorarPalavra = false;
for(int i = 0; i < array.length; i++) {
int indice = palavra.indexOf(array[i]);
if(indice != -1 && palavra.indexOf(array[i], indice+1) != -1){
ignorarPalavra = true;
i=array.length;
}
}
if(!ignorarPalavra) {
strBuilder.delete(0, strBuilder.length())
.append(contPalavraAtual + 1).append("/")
.append(totalPalavras).append(" --> ").append(palavra);
System.out.println(strBuilder.toString());
}
}
};
gerarPalavras(ascii, ascii.length(), ex);
}No teste que você passou na mensagem anterior, ele agora vai imprimir somente as entradas que fazem parte da permutação. Na verdade o algoritmo ainda está gerando todas as possibilidades, só que o listener ignora as que não fazem parte da permutação.
Certo. Gerar diretamente as permutações, em vez de gerar todas as combinações e escolher só as permutações, é a diferença entre você conseguir ou não gerar todas as permutações.
Digamos que você tenha 10 elementos. As permutações de 10 elementos são 10!, ou seja, 3.628.800 (um número razoavelmente pequeno, afinal de contas), enquanto as combinações de 10 elementos são 10^10 = 10.000.000.000 , que é um número 2756 vezes maior.
Se o valor passar para 15, você terá 1.307.674.368.000 (ainda viável em um computador pessoal - é claro que você não tentará gravar as combinações no seu disco) contra 437.893.890.380.859.375 , que é um valor completamente inviável, sem contar que esse valor é 334.864 vezes maior.
É verdade… O melhor é adaptar o algoritmo para gerar somente as permutações… Fica como exercício 
Depois quando tiver um tempo vou tentar adaptar o algoritmo para fazer da forma correta e posto aqui
Até mais!