Erzeugen Variationen ohne Wiederholungen / Permutationen in Java
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
muss ich ohne Ziffern gemacht Wiederholungen alle Variationen generieren 0 -. 9
Länge von ihnen von 1 bis 10 sein könnte, ich weiß wirklich nicht, wie es zu lösen, vor allem, wie Wiederholungen zu vermeiden.
Beispiel: Länge der Variante: 4 zufällige Variationen: 9856, 8753, 1243, 1234 usw. (aber nicht 9985 - enthalten Wiederholung)
Ich wäre wirklich dankbar, wenn mir jemand mit diesem Problem helfen kann, vor allem einige Code und Hinweise zu geben.
Lösung
Das Schlüsselwort zu suchen ist Permutation . Es gibt eine Fülle von Quellcode frei zur Verfügung, führt sie.
Was halten es Wiederholung befreien ich eine einfache rekursive Ansatz vorschlagen: für jede Ziffer, die Sie haben die Auswahl davon in Ihre Variation nehmen oder nicht, so dass Ihre Rekursion zählt durch die Ziffern und gabelt sich in zwei rekursive Aufrufe, eine, in der die digit enthalten ist, eines, bei dem es ausgeschlossen wird. Dann, nachdem die letzte Ziffer jeder Rekursion erreicht im Wesentlichen gibt Ihnen eine (einmalige, sortiert) Liste der Wiederholung freien Stellen. Anschließend können Sie alle möglichen Permutationen dieser Liste erstellen und alle diese Permutationen kombinieren, um Ihr Endergebnis zu erzielen.
(Das gleiche wie duffymo sagte: Ich werde keinen Code für die Versorgung)
Erweiterte Anmerkung: die Rekursion basiert auf 0/1 (Ausschluss, Inklusion), die direkt an Bits übersetzt werden kann, daher ganze Zahlen. Deshalb, um alle möglichen Zahlenkombinationen zu erhalten, ohne tatsächlich die Durchführung der Rekursion selbst Sie einfach alle Zahlen 10-Bit-Integer verwenden könnte und durchlaufen sie. Dann interpretiert die Zahlen sind, so dass ein Satz entspricht das Bit der Ziffer in der Liste darunter, dass permutiert werden muss.
Andere Tipps
Hier ist mein Java-Code. Fühlen Sie sich frei zu fragen, ob Sie nicht verstehen. Der wichtigste Punkt hier ist:
- Art wieder Zeichen-Array. zum Beispiel: a1 a2 a3 b1 b2 b3 .... (a1 = a2 = a3)
- erzeugen Permutation und immer halten Bedingung: Index von 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");
}
}
Ich habe den folgenden Code erstellte Permutationen zu erzeugen, wo Ordnung wichtig ist und ohne Wiederholung. Es macht Gebrauch von Generika für Permutation jede Art von Objekt:
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;
}
}
Stellen Sie sich eine magische Funktion hatte - eine Reihe von Ziffern angegeben, es wird Ihnen die richtigen Permutationen zurückzukehren.
Wie können Sie diese Funktion verwenden, um eine neue Liste von Permutationen mit nur einem zusätzlichen Stelle zu produzieren?
z. B.
Wenn ich Ihnen eine Funktion namens permute_three(char[3] digits), und ich Ihnen sagen, dass es funktioniert nur für Ziffern 0, 1, 2, wie können Sie eine Funktion schreiben, die 0 permutieren kann, 1, 2, 3, mit der gegebenen permute_three Funktion ?
...
, wenn Sie das gelöst, was fällt Ihnen auf? können Sie es verallgemeinern?
Dollar es ist einfach:
@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));
}
}
Es gibt eine Lösung, die nicht von mir ist, aber es ist sehr schön und anspruchsvoll.
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);
}
}
}
Ich denke, das ist die hervorragende Lösung.
Kurz hilfreich Permutation Indizierung Wissen
Erstellen Sie eine Methode, die die korrekte Permutation erzeugt, da ein Indexwert zwischen {0 und N! -1} für „Null indiziert“ oder {1 und N!} Für „einen indiziert“.
Erstellen einer zweiten Methode einer „for-Schleife“ enthält, wobei die untere Grenze 1 und der oberen Grenze ist N !. z .. "für (i; i <= N !; i ++)". für jede Instanz des Schleifen Anruf die erste Methode, i als Argument übergeben
