Permutazione della matrice

Ad esempio, ho questo array:

int a[] = new int[]{3,4,6,2,1}; 

Ho bisogno di una lista di tutte le permutazioni in modo tale che se uno è così, {3,2,1,4,6} , gli altri non devono essere uguali. So che se la lunghezza dell’array è n allora ci sono n! combinazioni possibili Come si può scrivere questo algoritmo?

Aggiornamento: grazie, ma ho bisogno di un algoritmo di pseudo codice come:

 for(int i=0;i<a.length;i++){ // code here } 

Solo algoritmo Sì, le funzioni API sono buone, ma non mi aiutano troppo.

Se stai usando C ++, puoi usare std::next_permutation dal file di intestazione :

 int a[] = {3,4,6,2,1}; int size = sizeof(a)/sizeof(a[0]); std::sort(a, a+size); do { // print a's elements } while(std::next_permutation(a, a+size)); 

Ecco come è ansible stampare tutte le permutazioni in 10 righe di codice:

 public class Permute{ static void permute(java.util.List arr, int k){ for(int i = k; i < arr.size(); i++){ java.util.Collections.swap(arr, i, k); permute(arr, k+1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() -1){ System.out.println(java.util.Arrays.toString(arr.toArray())); } } public static void main(String[] args){ Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0); } } 

Prendi il primo elemento di un array (k = 0) e lo scambia con qualsiasi elemento (i) dell'array. Quindi applichi ricorsivamente la permutazione sull'array iniziando dal secondo elemento. In questo modo ottieni tutte le permutazioni a partire dall'elemento i-esimo. La parte difficile è che dopo la chiamata ricorsiva devi scambiare l'elemento i-esimo con il primo elemento, altrimenti potresti ottenere valori ripetuti al primo punto. Scambiandolo, ripristiniamo l'ordine degli elementi (in pratica fai il backtracking).

Iteratori e estensione al caso di valori ripetuti

Lo svantaggio dell'algoritmo precedente è che è ricorsivo e non gioca bene con gli iteratori. Un altro problema è che se autorizzi elementi ripetuti nel tuo input, allora non funzionerà così com'è.

Ad esempio, dato input [3,3,4,4] tutte le possibili permutazioni (senza ripetizioni) lo sono

 [3, 3, 4, 4] [3, 4, 3, 4] [3, 4, 4, 3] [4, 3, 3, 4] [4, 3, 4, 3] [4, 4, 3, 3] 

(se applichi semplicemente la funzione di permutazione dall'alto otterrai [3,3,4,4] quattro volte, e questo non è ciò che vuoi vedere in questo caso, e il numero di tali permutazioni è 4! / (2 * 2!) = 6)

È ansible modificare l'algoritmo di cui sopra per gestire questo caso, ma non sarà bello. Fortunatamente, c'è un algoritmo migliore (l'ho trovato qui ) che gestisce i valori ripetuti e non è ricorsivo.

Innanzitutto, la permutazione della matrice di qualsiasi object può essere ridotta a permutazioni di numeri interi enumerandoli in qualsiasi ordine.

Per ottenere le permutazioni di un array intero, si inizia con un array ordinato in ordine crescente. Il tuo objective è renderlo discendente. Per generare la prossima permutazione, stai cercando di trovare il primo indice dal basso in cui la sequenza non riesce a scendere, e migliora il valore in quell'indice mentre si commuta l'ordine del resto della coda da decrescente ad ascendente in questo caso.

Ecco il nucleo dell'algoritmo:

 //ind is an array of integers for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } break; } } 

Ecco il codice completo di iteratore. Il costruttore accetta una matrice di oggetti e li mappa in una matrice di numeri interi utilizzando HashMap .

 import java.lang.reflect.Array; import java.util.*; class Permutations implements Iterator{ private E[] arr; private int[] ind; private boolean has_next; public E[] output;//next() returns this array, make it public Permutations(E[] arr){ this.arr = arr.clone(); ind = new int[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map hm = new HashMap(); for(int i = 0; i < arr.length; i++){ Integer n = hm.get(arr[i]); if (n == null){ hm.put(arr[i], i); n = i; } ind[i] = n.intValue(); } Arrays.sort(ind);//start with ascending sequence of integers //output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length); has_next = true; } public boolean hasNext() { return has_next; } /** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) throw new NoSuchElementException(); for(int i = 0; i < ind.length; i++){ output[i] = arr[ind[i]]; } //get next permutation has_next = false; for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } has_next = true; break; } } return output; } private void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void remove() { } } 

Uso / test:

  TCMath.Permutations perm = new TCMath.Permutations(new Integer[]{3,3,4,4,4,5,5}); int count = 0; while(perm.hasNext()){ System.out.println(Arrays.toString(perm.next())); count++; } System.out.println("total: " + count); 

Stampa tutto 7!/(2!*3!*2!)=210 permutazioni.

Ecco un’implementazione della permutazione in Java:

Permutazione – Java

Dovresti avere un controllo su di esso!

Modifica: codice incollato di seguito per proteggere da link-death:

 // Permute.java -- A class generating all permutations import java.util.Iterator; import java.util.NoSuchElementException; import java.lang.reflect.Array; public class Permute implements Iterator { private final int size; private final Object [] elements; // copy of original 0 .. size-1 private final Object ar; // array for output, 0 .. size-1 private final int [] permutation; // perm of nums 1..size, perm[0]=0 private boolean next = true; // int[], double[] array won't work :-( public Permute (Object [] e) { size = e.length; elements = new Object [size]; // not suitable for primitives System.arraycopy (e, 0, elements, 0, size); ar = Array.newInstance (e.getClass().getComponentType(), size); System.arraycopy (e, 0, ar, 0, size); permutation = new int [size+1]; for (int i=0; ipermutation[i+1]) i--; if (i==0) { next = false; for (int j=0; jpermutation[j]) j--; swap (i,j); int r = size; int s = i+1; while (r>s) { swap(r,s); r--; s++; } return ar; } public String toString () { final int n = Array.getLength(ar); final StringBuffer sb = new StringBuffer ("["); for (int j=0; j 

Questa è una permutazione a 2 per una lista racchiusa in un iteratore

 import java.util.Iterator; import java.util.LinkedList; import java.util.List; /* all permutations of two objects * * for ABC: AB AC BA BC CA CB * * */ public class ListPermutation implements Iterator { int index = 0; int current = 0; List list; public ListPermutation(List e) { list = e; } public boolean hasNext() { return !(index == list.size() - 1 && current == list.size() - 1); } public List next() { if(current == index) { current++; } if (current == list.size()) { current = 0; index++; } List output = new LinkedList(); output.add(list.get(index)); output.add(list.get(current)); current++; return output; } public void remove() { } } 

Ci sono n! permutazioni totali per la dimensione dell’array data n . Ecco il codice scritto in Java usando DFS.

 public List> permute(int[] nums) { List> results = new ArrayList>(); if (nums == null || nums.length == 0) { return results; } List result = new ArrayList<>(); dfs(nums, results, result); return results; } public void dfs(int[] nums, List> results, List result) { if (nums.length == result.size()) { List temp = new ArrayList<>(result); results.add(temp); } for (int i=0; i 

Per l'array di input [3,2,1,4,6], ce ne sono totalmente 5! = 120 possibili permutazioni che sono:

 [[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]] 

Spero che questo ti aiuti.

Esempio con matrice primitiva:

 public static void permute(int[] intArray, int start) { for(int i = start; i < intArray.length; i++){ int temp = intArray[start]; intArray[start] = intArray[i]; intArray[i] = temp; permute(intArray, start + 1); intArray[i] = intArray[start]; intArray[start] = temp; } if (start == intArray.length - 1) { System.out.println(java.util.Arrays.toString(intArray)); } } public static void main(String[] args){ int intArr[] = {1, 2, 3}; permute(intArr, 0); } 

Rappresentazione visuale della soluzione ricorsiva a 3 voci: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Abbattersi:

  1. Per una matrice di due elementi, esistono due permutazioni:
    • La matrice originale e
    • I due elementi si sono invertiti
  2. Per un array di tre elementi, esistono sei permutazioni:
    • Le permutazioni dei due elementi inferiori, quindi
    • Scambia gli oggetti 1 ° e 2 ° e le permutazioni dei due elementi inferiori
    • Scambia gli oggetti 1 ° e 3 ° e le permutazioni dei due elementi inferiori.
    • In sostanza, ognuno degli oggetti ottiene la sua chance nel primo slot

Una semplice implementazione java, fare riferimento a c ++ std::next_permutation :

 public static void main(String[] args){ int[] list = {1,2,3,4,5}; List> output = new Main().permute(list); for(List result: output){ System.out.println(result); } } public List> permute(int[] nums) { List> list = new ArrayList>(); int size = factorial(nums.length); // add the original one to the list List seq = new ArrayList(); for(int a:nums){ seq.add(a); } list.add(seq); // generate the next and next permutation and add them to list for(int i = 0;i < size - 1;i++){ seq = new ArrayList(); nextPermutation(nums); for(int a:nums){ seq.add(a); } list.add(seq); } return list; } int factorial(int n){ return (n==1)?1:n*factorial(n-1); } void nextPermutation(int[] nums){ int i = nums.length -1; // start from the end while(i > 0 && nums[i-1] >= nums[i]){ i--; } if(i==0){ reverse(nums,0,nums.length -1 ); }else{ // found the first one not in order int j = i; // found just bigger one while(j < nums.length && nums[j] > nums[i-1]){ j++; } //swap(nums[i-1],nums[j-1]); int tmp = nums[i-1]; nums[i-1] = nums[j-1]; nums[j-1] = tmp; reverse(nums,i,nums.length-1); } } // reverse the sequence void reverse(int[] arr,int start, int end){ int tmp; for(int i = 0; i <= (end - start)/2; i++ ){ tmp = arr[start + i]; arr[start + i] = arr[end - i]; arr[end - i ] = tmp; } } 

Fai così …

 import java.util.ArrayList; import java.util.Arrays; public class rohit { public static void main(String[] args) { ArrayList a=new ArrayList(); ArrayList b=new ArrayList(); b.add(1); b.add(2); b.add(3); permu(a,b); } public static void permu(ArrayList prefix,ArrayList value) { if(value.size()==0) { System.out.println(prefix); } else { for(int i=0;i a=new ArrayList(); a.addAll(prefix); a.add(value.get(i)); ArrayList b=new ArrayList(); b.addAll(value.subList(0, i)); b.addAll(value.subList(i+1, value.size())); permu(a,b); } } } }