permutación del conjunto

Question

Por ejemplo tengo esta matriz:

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

Necesito lista de todas las permutaciones de tal manera que si uno es así, {3,2,1,4,6}, otros no deben ser los mismos. Sé que si la longitud de la matriz es n, entonces hay n! combinaciones posibles. ¿Cómo se puede escribir este algoritmo?

Actualización: gracias, pero necesito un algoritmo pseudo código como:

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

algoritmo Justo. Sí, las funciones de la API son buenas, pero no me ayudan demasiado.

Answer 1

Si estás usando C++, puede utilizar std::next_permutation del archivo <algorithm> cabecera:

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)); 

Answer 2

Aquí es una implementación de la permutación en Java:

Permutation - Java

usted debe tener un cheque en eso!

Editar: código pegado a continuación para proteger contra el enlace de la muerte:

// 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; i<size+1; i++) { 
     permutation [i]=i; 
     } 
    } 

    private void formNextPermutation() { 
     for (int i=0; i<size; i++) { 
     // i+1 because perm[0] always = 0 
     // perm[]-1 because the numbers 1..size are being permuted 
     Array.set (ar, i, elements[permutation[i+1]-1]); 
     } 
    } 

    public boolean hasNext() { 
     return next; 
    } 

    public void remove() throws UnsupportedOperationException { 
     throw new UnsupportedOperationException(); 
    } 

    private void swap (final int i, final int j) { 
     final int x = permutation[i]; 
     permutation[i] = permutation [j]; 
     permutation[j] = x; 
    } 

    // does not throw NoSuchElement; it wraps around! 
    public Object next() throws NoSuchElementException { 

     formNextPermutation(); // copy original elements 

     int i = size-1; 
     while (permutation[i]>permutation[i+1]) i--; 

     if (i==0) { 
     next = false; 
     for (int j=0; j<size+1; j++) { 
      permutation [j]=j; 
     } 
     return ar; 
     } 

     int j = size; 

     while (permutation[i]>permutation[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<n; j++) { 
     sb.append (Array.get(ar,j).toString()); 
     if (j<n-1) sb.append (","); 
     } 
     sb.append("]"); 
     return new String (sb); 
    } 

    public static void main (String [] args) { 
     for (Iterator i = new Permute(args); i.hasNext();) { 
     final String [] a = (String []) i.next(); 
     System.out.println (i); 
     } 
    } 
} 

Answer 3

Este a 2 de permutación para obtener una lista envuelto en un iterador

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<T> implements Iterator { 

    int index = 0; 
    int current = 0; 
    List<T> list; 

    public ListPermutation(List<T> e) { 
     list = e; 
    } 

    public boolean hasNext() { 
     return !(index == list.size() - 1 && current == list.size() - 1); 
    } 

    public List<T> next() { 
     if(current == index) { 
      current++; 
     } 
     if (current == list.size()) { 
      current = 0; 
      index++; 
     } 
     List<T> output = new LinkedList<T>(); 
     output.add(list.get(index)); 
     output.add(list.get(current)); 
     current++; 
     return output; 
    } 

    public void remove() { 
    } 

} 

Answer 4

Aquí es cómo puede imprimir todas las permutaciones en 10 líneas de código:

public class Permute{ 
    static void permute(java.util.List<Integer> 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); 
    } 
} 

Toma el primer elemento de una matriz (k = 0) y lo intercambia con cualquier elemento (i) de la matriz. Luego aplica de forma recursiva la permutación en la matriz comenzando con el segundo elemento. De esta manera, obtienes todas las permutaciones que comienzan con el elemento i-ésimo. La parte difícil es que después de la llamada recursiva debe intercambiar el elemento i-ésimo con el primer elemento, de lo contrario podría obtener valores repetidos en el primer punto. Al intercambiarlo de vuelta, restauramos el orden de los elementos (básicamente, haces un seguimiento).

iteradores y extensión al caso de valores repetidos

El inconveniente de algoritmo anterior es que es recursivo, y no juega muy bien con iteradores. Otro problema es que si permite elementos repetidos en su entrada, entonces no funcionará como está.

Por ejemplo, entrada dada [3,3,4,4] todas las permutaciones posibles (sin repeticiones) son

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

(si aplica simplemente permute función desde arriba obtendrá [3,3, 4,4] cuatro veces, y esto no es lo que naturalmente desea ver en este caso, y el número de tales permutaciones es 4!/(2! * 2!) = 6)

Es posible modificar el algoritmo anterior para manejar este caso, pero no se verá bien. Afortunadamente, hay un algoritmo mejor (lo encontré here) que maneja valores repetidos y no es recursivo.

Primero tenga en cuenta que la permutación de la matriz de cualquier objeto se puede reducir a permutaciones de enteros al enumerarlos en cualquier orden.

Para obtener las permutaciones de una matriz entera, se comienza con una matriz ordenada en orden ascendente. Tu 'objetivo' es hacer que descienda. Para generar la siguiente permutación, intenta encontrar el primer índice desde la parte inferior donde la secuencia no puede descender, y mejora el valor en ese índice mientras cambia el orden del resto de la cola de descendente a ascendente en este caso.

He aquí el núcleo del 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; 
    } 
} 

Aquí está el código completo del iterador. Constructor acepta una matriz de objetos y los mapea en una matriz de enteros usando HashMap.

import java.lang.reflect.Array; 
import java.util.*; 
class Permutations<E> implements Iterator<E[]>{ 

    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<E, Integer> hm = new HashMap<E, Integer>(); 
     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<Integer> perm = new TCMath.Permutations<Integer>(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); 

Imprime todas las permutaciones 7!/(2!*3!*2!)=210.

Answer 5

Visual representación de la 3-item solución recursiva: http://www.docdroid.net/ea0s/generatepermutations.pdf.html

Desglose:

1. Para una matriz de dos artículo, hay dos permutaciones:
   • la matriz original, y
   • Los dos elementos intercambiaron
2. Para una matriz de tres ítems, hay seis permutaciones:
   • Las permutaciones de los dos elementos de fondo, entonces
   • Intercambio de 1º y 2º artículos, y las permutaciones de los dos elemento inferior
   • Intercambiar primera y tercera artículos y las permutaciones de los dos elementos inferiores.
   • Esencialmente, cada uno de los elementos obtiene su oportunidad en la primera ranura

Answer 6

Hay n! permutaciones totales para el tamaño de la matriz dada n. Aquí hay un código escrito en Java usando DFS.

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

public void dfs(int[] nums, List<List<Integer>> results, List<Integer> result) { 
    if (nums.length == result.size()) { 
     List<Integer> temp = new ArrayList<>(result); 
     results.add(temp); 
    }   
    for (int i=0; i<nums.length; i++) { 
     if (!result.contains(nums[i])) { 
      result.add(nums[i]); 
      dfs(nums, results, result); 
      result.remove(result.size() - 1); 
     } 
    } 
} 

Para la matriz de entrada [3,2,1,4,6], hay totalmente 5! = 120 posibles permutaciones que son:

[[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]] 

Espero que esto ayude.

Answer 7

Una sencilla aplicación Java, consulte C++ std::next_permutation:

public static void main(String[] args){ 
    int[] list = {1,2,3,4,5}; 
    List<List<Integer>> output = new Main().permute(list); 
    for(List result: output){ 
     System.out.println(result); 
    } 

} 

public List<List<Integer>> permute(int[] nums) { 
    List<List<Integer>> list = new ArrayList<List<Integer>>(); 
    int size = factorial(nums.length); 

    // add the original one to the list 
    List<Integer> seq = new ArrayList<Integer>(); 
    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<Integer>(); 
     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; 
    } 
} 

Answer 8

Ejemplo con matriz 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); 
} 

Answer 9

hacer como esto ...

import java.util.ArrayList; 
import java.util.Arrays; 

public class rohit { 

    public static void main(String[] args) { 
     ArrayList<Integer> a=new ArrayList<Integer>(); 
     ArrayList<Integer> b=new ArrayList<Integer>(); 
     b.add(1); 
     b.add(2); 
     b.add(3); 
     permu(a,b); 
    } 

    public static void permu(ArrayList<Integer> prefix,ArrayList<Integer> value) 
    { 
     if(value.size()==0) 
     { 
      System.out.println(prefix); 
     } 
     else 
     { 
      for(int i=0;i<value.size();i++) 
      { 
       ArrayList<Integer> a=new ArrayList<Integer>(); 
       a.addAll(prefix); 
       a.add(value.get(i)); 

       ArrayList<Integer> b=new ArrayList<Integer>(); 

       b.addAll(value.subList(0, i)); 
       b.addAll(value.subList(i+1, value.size())); 

       permu(a,b); 
      } 
     } 
    } 

}