Variaciones de generación sin repeticiones / permutaciones en java
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo para generar todas las variaciones sin repeticiones hecho de dígitos 0 -. 9
Longitud de ellos podría ser de 1 a 10. Realmente no sé cómo resolverlo, especialmente la forma de evitar repeticiones.
Ejemplo: longitud de variaciones: 4 variaciones aleatorias: 9856, 8753, 1243, 1234 etc. (pero no 9985 - contiene repetición)
Yo estaría muy agradecido si alguien me puede ayudar con este tema, sobre todo dando algo de código y las pistas.
Solución
La palabra clave para buscar es permutación . Hay una gran cantidad de código fuente disponible libremente que los realiza.
En cuanto a mantenerla repetición libre que sugieren un enfoque recursivo simple: para cada dígito tiene la opción de tomarlo en su variación o no, por lo que su recursividad cuenta a través de los números y se bifurca en dos llamadas recursivas, uno en el que la se incluye dígitos, una en la que se excluye. Entonces, después de que llegó a la última cifra cada recursividad esencialmente le da una lista (única, ordenada) de dígitos sin repetición. A continuación, puede crear todas las permutaciones posibles de esta lista y combinar todas esas permutaciones hasta conseguir el resultado final.
(Lo mismo que dijo duffymo: No voy a suministrar código para eso)
nota avanzada: la recursión se basa en 0/1 (exclusión, la inclusión), que directamente puede ser traducido a los bits, por lo tanto, números enteros. Por lo tanto, con el fin de obtener todas las posibles combinaciones de dígitos sin realizar la recursividad en sí simplemente podría utilizar todos los números enteros de 10 bits e iterar a través de ellos. A continuación, interpretar los números de tal manera que un conjunto de bits corresponde a incluir el dígito en la lista que necesita ser permutada.
Otros consejos
Aquí está mi código Java. No dude en preguntar si no entiende. El punto principal aquí es:
- especie de nuevo array de caracteres. por ejemplo: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
- permutación generar y mantener siempre la condición: Í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");
}
}
He creado el siguiente código para generar permutaciones las que el orden es importante y sin repetición. Se hace uso de los genéricos para permutar cualquier 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 tiene una función mágica - dada una serie de dígitos, se le devolverá las permutaciones correctas.
¿Cómo puede usar esta función para producir una nueva lista de permutaciones con un solo dígito adicional?
por ejemplo.,
Si le diera una función llamada permute_three(char[3] digits), y te digo que sólo funciona para 0 dígitos, 1, 2, ¿cómo se puede escribir una función que puede permutar 0, 1, 2, 3, utilizando la función permute_three dada ?
...
Una vez que se resolvió el, ¿Qué notas? se puede generalizar?
Dólar es simple:
@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));
}
}
El código para esta es similar a la que sin duplicados, con la adición de un statement.Check si-else esta código
En el código anterior, editar el bucle como sigue
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;
}
funcionado para mí
Permutación sin repetición se basa en el teorema, que cantidad de resultados es factorial de recuento de elementos (en este caso números). En su caso 10! es 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. La prueba por lo que es exactamente adecuado es solución adecuada para la generación también. Pues entonces, ¿cómo. En primera posición, es decir de izquierda que puede tener 10 números, en la segunda posición se puede tener sólo 9 números, porque un número está en la posición de la izquierda y que no se puede repetir el mismo número, etc. (la prueba se hace por inducción matemática ). Entonces, ¿cómo generar diez primeros resultados? Según mis conocimientos, que forma más sencilla es utilizar desplazamiento cíclico. Esto significa que el número de orden de giro a la izquierda en una posición (o la derecha si quieres) y el número de los cuales desbordamiento para poner en el lugar vacío. Esto significa para los diez primeros resultados:
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
...
La primera línea es la muestra básica, por lo que es la buena idea de ponerlo en conjunto antes de la generación. Ventaja es, que en el siguiente paso que tendrá que resolver el mismo problema de evitar duplicidades indeseables.
En la siguiente etapa de forma recursiva gire sólo 10-1 números 10-1 veces etc. Esto significa para los primeros 9 resultados en el paso dos:
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 la primera línea está presente desde el paso anterior, por lo que no se debe añadir a generado establecer de nuevo.
El algoritmo de forma recursiva hacer exactamente eso, lo que se explicó anteriormente. Es posible generar todas las combinaciones 3628800 de 10 !, porque el número de anidación es el mismo que el número de elementos en la matriz (que significa en su caso para 10 números que se retrasa unos 5 minutos. En mi equipo) y que necesita tener suficiente memoria Si desea mantener todas las combinaciones en serie.
Hay solución.
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);
}
}
Intensidad (número de ciclos) de algoritmo es suma de factoriales incompletos de número de miembros. Así que hay voladizo conjunto parcial cuando se lee de nuevo para generar siguiente subconjunto, por lo que la intensidad es:
n! + N! / 2! + N! / 3! + ... + n! / (N-2)! + N! (N-1)!
Hay una solución que no es de la mía, pero es muy agradable y 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);
}
}
}
Creo que, esta es la solución excelente.
Breve útiles permutación de indexación Conocimiento
Crea un método que genera la permutación correcta, dado un valor de índice entre {0 y N! -1} para "cero indexadas" o {1 y N!} Para "uno indexadas".
Crea un segundo método que contiene un "bucle", donde el límite inferior es 1 y el límite superior es N !. por ejemplo ... "para (i; i <= N !; i ++)" para cada instancia del bucle llamar el primer método, pasando i como el argumento
