Variazioni generatrici senza ripetizioni / permutazioni in java
https://stackoverflow.com/questions/1900197
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho generare tutte le varianti senza ripetizioni fatte di cifre 0 -. 9
Lunghezza di loro potrebbe essere da 1 a 10. Io davvero non so come risolverlo, soprattutto come evitare ripetizioni.
Esempio: lunghezza delle variazioni: 4 variazioni casuali: 9856, 8753, 1243, 1234, ecc (ma non 9985 - contiene ripetizione)
sarei davvero grato se qualcuno mi può aiutare in questo problema, in particolare dando qualche codice e indizi.
Soluzione
La parola chiave da cercare è permutazione . C'è un'abbondanza di codice sorgente liberamente disponibile che li esegue.
Per quanto riguarda mantenendolo ripetizione libero mi suggerire un semplice approccio ricorsivo: per ogni cifra si dispone di una scelta di prendere nella tua variante o no, in modo che il ricorsione conta tra le cifre e le forchette in due chiamate ricorsive, quello in cui il cifre è inclusa, quella in cui è escluso. Poi, dopo aver raggiunto l'ultima cifra ogni ricorsione ti dà essenzialmente un (unico ordinato,) Lista di cifre senza ripetizione. È quindi possibile creare tutte le possibili permutazioni di questa lista e combinare tutte queste permutazioni per raggiungere il risultato finale.
(Come detto duffymo: Non fornire il codice per questo)
Nota avanzata: la ricorsione si riferiscono al 0/1 (esclusione, inclusione) che può direttamente essere tradotto bit, quindi, numeri interi. Pertanto, al fine di ottenere tutte le possibili combinazioni di cifre senza effettivamente eseguire la ricorsione in sé si potrebbe semplicemente utilizzare tutti i numeri interi a 10 bit e iterare attraverso di loro. Poi interpretare i numeri in modo tale che un po 'impostato corrisponde al compresa la cifra nella lista che deve essere permutata.
Altri suggerimenti
Ecco il mio codice Java. Sentitevi liberi di chiedere se non si capisce. Il punto principale è:
- sorta di nuovo array di caratteri. per esempio: A1 A2 A3 B1 B2 B3 .... (a1 = a2 = a3)
- generare permutazione e tenere sempre condizioni: indice della 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");
}
}
Ho creato il seguente codice per la generazione di permutazioni in cui ordinamento è importante e senza ripetizione. Si avvale di farmaci generici per la permutazione qualsiasi tipo di oggetto:
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;
}
}
Immagina di avere una funzione magica - dato un array di cifre, lo restituirà le permutazioni corrette.
Come si può utilizzare questa funzione per produrre un nuovo elenco di permutazioni con un solo cifre extra?
per es.,
se mi avete dato da una funzione chiamata permute_three(char[3] digits), e vi dico che funziona solo per 0 cifre, 1, 2, come si può scrivere una funzione che può permutare 0, 1, 2, 3, utilizzando la funzione data permute_three ?
...
Una volta risolto questo, cosa notate? si può generalizzare?
Dollaro è semplice:
@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 codice per questo è simile a quella senza duplicati, con l'aggiunta di uno statement.Check if-else questo codice
Nel codice precedente, Modificare il ciclo for come 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;
}
funzionato per me
Permutazione senza ripetizione si riferiscono al teorema, quella quantità di risultati è fattoriale di conteggio di elementi (in questo caso numeri). Nel tuo caso 10! è 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. La prova per questo che è esattamente di destra è la soluzione giusta per la generazione anche. Ebbene sì, come. Sulla prima posizione cioè da sinistra si può avere 10 numeri, in seconda posizione si può avere solo 9 numeri, perché un numero è sulla posizione di sinistra e non possiamo ripetere lo stesso numero, ecc (la prova è fatta per induzione ). Così come generare primi dieci risultati? Secondo le mie conoscenze, egli più semplice modo è quello di utilizzare spostamento ciclico. Significa l'ordine di numero di spostamento a sinistra su una posizione (o destra se volete) e il numero che overflow per mettere sul posto vuoto. Significa per i primi dieci risultati:
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 prima linea è campione di base, quindi è la buona idea di metterlo in impostato prima generazione. Vantaggio è che nella fase successiva si dovrà risolvere lo stesso problema per evitare doppioni indesiderabili.
Nella fase successiva ricorsivamente solo ruotare 10-1 numeri 10-1 volte etc. Significa per primi 9 risultati nel passaggio due:
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
...
ecc, avviso, che la prima linea è presente dal passo precedente, quindi non deve essere aggiunto generato impostare nuovamente.
L'algoritmo ricorsivo fare esattamente questo, ciò che viene spiegato in precedenza. E 'possibile generare tutte le combinazioni per 3628800 10 !, perché il numero di nidificazione è la stessa numero di elementi array (che significa nel tuo caso per 10 numeri indugia circa 5 minuti. Sul mio computer) ed è necessario disporre di memoria sufficiente se si desidera mantenere tutte le combinazioni in serie.
Non c'è soluzione.
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);
}
}
intensità (numero di cicli) di algoritmo è somma dei fattoriali incompleti di numero di membri. Quindi non v'è sbalzo quando set parziale è di nuovo letto per generare prossimo sottoinsieme, quindi intensità è:
n! + N! / 2! + N! / 3! + ... + n! / (N-2)! + N! (N-1)!
C'è una soluzione che non è dalla mia, ma è molto bello e sofisticato.
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);
}
}
}
Credo che, questa è la soluzione eccellente.
Brief utili permutazione indicizzazione Conoscenza
Creare un metodo che genera la permutazione corretta, dato un valore di indice compreso tra {0 e N! -1} per "zero indicizzati" o {1 e N!} Per "uno indicizzato".
Creare un secondo metodo contenente un "ciclo for" dove il limite inferiore è 1 e il limite superiore è N !. es ... "per (i; i <= N !; i ++)" per ogni istanza del ciclo chiamare il primo metodo, passando i come argomento
