Variações geradoras sem repetições / permutações em Java
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho que gerar todas as variações, sem repetições feito dos dígitos 0 -. 9
Comprimento deles poderia ser de 1 a 10. Eu realmente não sei como resolvê-lo, especialmente como evitar repetições.
Exemplo: comprimento de variações: 4 variações aleatórias: 9856, 8753, 1243, 1234 etc. (mas não 9985 - contém repetição)
Eu ficaria muito grato se alguém pode me ajudar com essa questão, especialmente dando algum código e pistas.
Solução
A palavra-chave é a olhar para permutação . Há uma abundância de código-fonte livremente disponível que executa-los.
Como para mantê-lo repetição libertar Sugiro uma abordagem recursiva simples: para cada dígito você tem uma escolha de levá-lo em sua variação ou não, então as suas contagens de recursão através dos dígitos e garfos em duas chamadas recursivas, no qual o dígitos está incluído, no qual ele é excluído. Então, depois de alcançado o último dígito de cada recursão essencialmente dá-lhe uma lista (única, classificado) de dígitos sem repetição. Você pode então criar todas as permutações possíveis dessa lista e combinar todas essas permutações para alcançar o resultado final.
(O mesmo que duffymo disse: Eu não vai fornecer o código para isso)
Nota avançada: a recursividade baseia-se 0/1 (exclusão, inclusão) que podem ser directamente traduzidos para bits, assim, números inteiros. Portanto, a fim de obter todas as combinações possíveis de dígitos sem realmente executar o próprio recursão você poderia simplesmente usar todos os números inteiros de 10 bits e iterate através deles. Então interpretar os números de tal forma que um conjunto de bits corresponde a incluindo o dígito na lista que precisa ser permutado.
Outras dicas
Aqui está o meu código Java. Sinta-se livre para perguntar se você não entende. O ponto principal aqui é:
- tipo novo array de caracteres. por exemplo: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
- gerar permutação e sempre manter a condição: índice de a1 <índice de a2 <índice de a3 ...
import java.util.Arrays;
public class PermutationDup {
public void permutation(String s) {
char[] original = s.toCharArray();
Arrays.sort(original);
char[] clone = new char[s.length()];
boolean[] mark = new boolean[s.length()];
Arrays.fill(mark, false);
permute(original, clone, mark, 0, s.length());
}
private void permute(char[] original, char[] clone, boolean[] mark, int length, int n) {
if (length == n) {
System.out.println(clone);
return;
}
for (int i = 0; i < n; i++) {
if (mark[i] == true) continue;
// dont use this state. to keep order of duplicate character
if (i > 0 && original[i] == original[i-1] && mark[i-1] == false) continue;
mark[i] = true;
clone[length] = original[i];
permute(original, clone, mark, length+1, n);
mark[i] = false;
}
}
public static void main(String[] args) {
PermutationDup p = new PermutationDup();
p.permutation("abcab");
}
}
Eu criei o seguinte código para a geração de permutações onde ordenação é importante e sem repetição. Ele faz uso de genéricos para permutar qualquer tipo de objeto:
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Permutations {
public static <T> Collection<List<T>> generatePermutationsNoRepetition(Set<T> availableNumbers) {
Collection<List<T>> permutations = new HashSet<>();
for (T number : availableNumbers) {
Set<T> numbers = new HashSet<>(availableNumbers);
numbers.remove(number);
if (!numbers.isEmpty()) {
Collection<List<T>> childPermutations = generatePermutationsNoRepetition(numbers);
for (List<T> childPermutation : childPermutations) {
List<T> permutation = new ArrayList<>();
permutation.add(number);
permutation.addAll(childPermutation);
permutations.add(permutation);
}
} else {
List<T> permutation = new ArrayList<>();
permutation.add(number);
permutations.add(permutation);
}
}
return permutations;
}
}
Imagine que você tinha uma função mágica - dada uma série de dígitos, ele irá retornar as permutações corretas.
Como você pode usar essa função para produzir uma nova lista de permutações com apenas um dígito extra?
por exemplo.,
Se eu lhe desse uma função chamada permute_three(char[3] digits), e eu dizer-lhe que ele só funciona para 0 dígitos, 1, 2, como você pode escrever uma função que pode permutar 0, 1, 2, 3, usando a função permute_three dada ?
...
Uma vez que você resolveu isso, o que você observa? você pode generalizar isso?
Dollar é simples:
@Test
public void generatePermutations() {
// digits is the string "0123456789"
String digits = $('0', '9').join();
// then generate 10 permutations
for (int i : $(10)) {
// shuffle, the cut (0, 4) in order to get a 4-char permutation
System.out.println($(digits).shuffle().slice(4));
}
}
O código para isso é semelhante ao que sem duplicatas, com a adição de um statement.Check if-else este código
No código acima, Editar do loop for como se segue
for (j = i; j <= n; j++)
{
if(a[i]!=a[j] && !is_duplicate(a,i,j))
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j));
}
else if(i!=j) {} // if no duplicate is present , do nothing
else permute(a,i+1,n); // skip the ith character
}
bool is_duplicate(int *a,int i,int j)
{
if a[i] is present between a[j]...a[i]
return 1;
otherwise
return 0;
}
funcionou para mim
Permutation sem repetição é baseada no teorema, que a quantidade de resultados é fatorial de contagem de elementos (neste número de casos). No seu caso 10! é 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. A prova por isso que é exactamente à direita é a solução ideal para geração também. Bem assim como. Na primeira ie posição da esquerda você pode ter 10 números, na segunda posição, você pode ter apenas 9 números, porque um número está na posição à esquerda e não podemos repetir o mesmo número etc. (a prova é feita por indução matemática ). Então, como para gerar os primeiros resultados de dez? De acordo com meus conhecimentos, ele maneira mais simples é usar o desvio cíclico. Isso significa que a ordem do número do desvio para a esquerda em uma posição (ou à direita se você quiser) eo número que transbordam para colocar no lugar vazio. Isso significa para os resultados do primeiro dez:
10 9 8 7 6 5 4 3 2 1 | 9 8 7 6 5 4 3 2 1 10
8 7 6 5 4 3 2 1 10 9
7 6 5 4 3 2 1 10 9 8
6 5 4 3 2 1 10 9 8 7
5 4 3 2 1 10 9 8 7 6
...
A primeira linha é amostra básica, por isso é a boa idéia para colocá-lo em conjunto antes da geração. A vantagem é que, no próximo passo que você terá que resolver o mesmo problema para evitar duplicidades indesejáveis.
Na etapa seguinte forma recursiva girar apenas 10-1 números 10-1 vezes etc. Isso significa que para os primeiros 9 resultados em etapa dois:
10 9 8 7 6 5 4 3 2 1 | 10 8 7 6 5 4 3 2 1 9
10 7 6 5 4 3 2 1 9 8
10 6 5 4 3 2 1 9 8 7
10 5 4 3 2 1 9 8 7 6
...
etc, aviso, que a primeira linha está presente a partir do passo anterior, de modo que não deve ser adicionado ao conjunto gerado de novo.
Algoritmo de forma recursiva fazendo exatamente isso, o que é explicado acima. É possível gerar todos os 3628800 combinações para 10 !, porque o número de nidificação é o mesmo que o número de elementos no array (que significa no seu caso para 10 números atrasa-se cerca de 5min. No meu computador) e você precisa ter memória suficiente Se você quiser manter todas as combinações na matriz.
Não há solução.
package permutation;
/** Class for generation amount of combinations (factorial)
* !!! this is generate proper permutations without repeating and proper amount (počet) of rows !!!
*
* @author hariprasad
*/
public class TestForPermutationII {
private static final String BUMPER = "*";
private static int counter = 0;
private static int sumsum = 0;
// definitoin of array for generation
//int[] testsimple = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] testsimple = {1, 2, 3, 4, 5};
private int ELEMNUM = testsimple.length;
int[][] shuff;
private String gaps(int len) {
String addGap = "";
for(int i=0; i <len; i++)
addGap += " ";
return addGap;
}
/** Factorial computing */
private int fact(int num) {
if (num > 1) {
return num * fact(num - 1);
} else {
return 1;
}
}
/** Cyclic shift position to the left */
private int[] lShiftPos(int[] arr, int pos) {
int[] work = new int[ELEMNUM];
int offset = -1;
for (int jj = 0; jj < arr.length; jj++) {
if (jj < pos) {
work[jj] = arr[jj];
} else if (jj <= arr.length - 1) {
if (jj == pos) {
offset = arr[pos]; // last element
}
if (jj != (arr.length - 1)) {
work[jj] = arr[jj + 1];
} else {
work[jj] = offset;
}
}
}
return work;
}
private String printBuff(int[] buffer) {
String res = "";
for (int i= 0; i < buffer.length; i++) {
if (i == 0)
res += buffer[i];
else
res += ", " + buffer[i];
}
return res;
};
/** Recursive generator for arbitrary length of array */
private String permutationGenerator(int pos, int level) {
String ret = BUMPER;
int templen = counter;
int[] work = new int[ELEMNUM];
int locsumread = 0;
int locsumnew = 0;
//System.out.println("\nCalled level: " + level);
for (int i = 0; i <= templen; i++) {
work = shuff[i];
sumsum++;
locsumread++;
for (int ii = 0; ii < pos; ii++) {
counter++;
sumsum++;
locsumnew++;
work = lShiftPos(work, level); // deep copy
shuff[counter] = work;
}
}
System.out.println("locsumread, locsumnew: " + locsumread + ", " + locsumnew);
// if level == ELEMNUM-2, it means no another shift
if (level < ELEMNUM-2) {
ret = permutationGenerator(pos-1, level+1);
ret = "Level " + level + " end.";
//System.out.println(ret);
}
return ret;
}
public static void main(String[] argv) {
TestForPermutationII test = new TestForPermutationII();
counter = 0;
int len = test.testsimple.length;
int[] work = new int[len];
test.shuff = new int[test.fact(len)][];
//initial
test.shuff[counter] = test.testsimple;
work = test.testsimple; // shalow copy
test.shuff = new int[test.fact(len)][];
counter = 0;
test.shuff[counter] = test.testsimple;
test.permutationGenerator(len-1, 0);
for (int i = 0; i <= counter; i++) {
System.out.println(test.printBuff(test.shuff[i]));
}
System.out.println("Counter, cycles: " + counter + ", " + sumsum);
}
}
Intensidade (número de ciclos) do algoritmo é soma de fatoriais incompletas do número de membros. Portanto, não há excesso quando conjunto parcial é lido novamente para gerar próxima subconjunto, então intensidade é:
n! + N! / 2! + N! / 3! + ... + n! / (N-2)! + N! (N-1)!
Há uma solução que não é da minha, mas é muito agradável e sofisticado.
package permutations;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
/**
* @author Vladimir Hajek
*
*/
public class PermutationSimple {
private static final int MAX_NUMBER = 3;
Set<String> results = new HashSet<>(0);
/**
*
*/
public PermutationSimple() {
// TODO Auto-generated constructor stub
}
/**
* @param availableNumbers
* @return
*/
public static List<String> generatePermutations(Set<Integer> availableNumbers) {
List<String> permutations = new LinkedList<>();
for (Integer number : availableNumbers) {
Set<Integer> numbers = new HashSet<>(availableNumbers);
numbers.remove(number);
if (!numbers.isEmpty()) {
List<String> childPermutations = generatePermutations(numbers);
for (String childPermutation : childPermutations) {
String permutation = number + childPermutation;
permutations.add(permutation);
}
} else {
permutations.add(number.toString());
}
}
return permutations;
}
/**
* @param args
*/
public static void main(String[] args) {
Set<Integer> availableNumbers = new HashSet<>(0);
for (int i = 1; i <= MAX_NUMBER; i++) {
availableNumbers.add(i);
}
List<String> permutations = generatePermutations(availableNumbers);
for (String permutation : permutations) {
System.out.println(permutation);
}
}
}
Eu acho que, esta é a solução excelente.
conhecimento breve útil permutação indexação
Crie um método que gera a permutação correta, dado um valor de índice entre {0 e N! -1} para "zero, indexado" ou {1 e N!} Para "um indexado".
Criar um segundo método que contém um "loop", em que o limite inferior é de 1 e o limite superior é N !. ex .. "para (i; i <= N !; i ++)". para cada instância da chamada ansa o primeiro método, a passagem de i como o argumento
