Les variations de production sans répétitions / Permutations en java
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je dois générer toutes les variantes sans répétitions en chiffres 0 - 9.
Longueur d'entre eux pourrait être de 1 à 10. Je ne sais vraiment pas comment le résoudre, en particulier comment éviter les répétitions.
Exemple: longueur de variations: 4 variations aléatoires: 9856, 8753, 1243, 1234, etc. (mais pas 9985 - contient la répétition)
Je serais vraiment reconnaissant si quelqu'un peut me aider avec cette question, en particulier de donner un code et des indices.
La solution
Le mot-clé à rechercher est permutation . Il y a une abondance de code source librement disponible qui les exécute.
Quant à garder la répétition libre, je suggère une approche récursive simple: pour chaque chiffre que vous avez le choix de le prendre dans votre variation ou non, de sorte que votre récursion compte par les chiffres et les fourchettes en deux appels récursifs, un dans lequel le chiffre est inclus, une dans laquelle elle est exclue. Puis, après avoir atteint le dernier chiffre chaque récursion vous donne essentiellement une (unique, triés) liste des chiffres sans répétition. Vous pouvez ensuite créer toutes les permutations possibles de cette liste et de combiner toutes ces permutations pour obtenir votre résultat final.
(Comme duffymo dit: Je ne vais pas fournir le code pour cela)
Note avancée: la récursion est basée sur 0/1 (exclusion, inclusion) qui peut être directement traduit en bits, par conséquent, des nombres entiers. Par conséquent, afin d'obtenir toutes les combinaisons possibles de chiffres sans réellement effectuer la récursion lui-même, vous pouvez simplement utiliser tous les nombres entiers 10 bits et itérer à travers eux. interpréter ensuite les nombres tels qu'un bit de jeu correspond à inclure le chiffre dans la liste qui doit être permuté.
Autres conseils
Voici mon code Java. Ne hésitez pas à demander si vous ne comprenez pas. Le point principal est ici:
- trier à nouveau tableau de caractères. par exemple: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
- générer permutation et toujours garder l'état: indice de a1
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");
}
}
J'ai créé le code suivant pour générer des permutations où la commande est importante et sans répétition. Il utilise des médicaments génériques pour permutant tout type d'objet:
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;
}
}
Imaginez que vous aviez une fonction magique - donné un tableau de chiffres, il vous renvoie les permutations correctes.
Comment pouvez-vous utiliser cette fonction pour produire une nouvelle liste de permutations avec un seul chiffre supplémentaire?
par ex.,
si je vous ai donné une fonction appelée permute_three(char[3] digits), et je vous dis que cela ne fonctionne que pour 0 chiffres, 1, 2, comment pouvez-vous écrire une fonction qui peut permute 0, 1, 2, 3, en utilisant la fonction permute_three donnée ?
...
une fois que vous avez résolu que, que remarquez-vous? pouvez-vous généraliser?
Dollar est 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));
}
}
Il y a une solution qui ne soit pas de la mienne, mais il est très agréable et sophistiqué.
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);
}
}
}
Je pense que, c'est l'excellente solution.
indexation Brève permutation des connaissances utiles
Insérer un procédé qui génère la permutation correcte, étant donné une valeur d'indice entre 0 et N {! -1} pour « zéro indexé » ou {1 et N!} Pour « une indexation ».
Créer une seconde méthode contenant une « boucle », où la limite inférieure est 1 et la limite supérieure est N !. ex .. "(i; i <= N !; i ++)" pour chaque instance de la boucle appeler le premier procédé, i passant comme argument
