Java Código para las permutaciones de una lista de números

Question

He escrito un programa para encontrar todas las permutaciones posibles de una lista dada de elementos. Esto significa precisamente que mis impresiones del programa es posible P (n, r) los valores para r = 0 an

A continuación se muestra el código:

package com.algorithm; 

import java.util.ArrayList; 
import java.util.Calendar; 
import java.util.Collection; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 

public class Permutations<T> { 
    public static void main(String args[]) { 
     Permutations<Integer> obj = new Permutations<Integer>(); 
     Collection<Integer> input = new ArrayList<Integer>(); 
     input.add(1); 
     input.add(2); 
     input.add(3); 

     Collection<List<Integer>> output = obj.permute(input); 
     int k = 0; 
     Set<List<Integer>> pnr = null; 
     for (int i = 0; i <= input.size(); i++) { 
      pnr = new HashSet<List<Integer>>(); 
      for(List<Integer> integers : output){ 
      pnr.add(integers.subList(i, integers.size())); 
      } 
      k = input.size()- i; 
      System.out.println("P("+input.size()+","+k+") :"+ 
      "Count ("+pnr.size()+") :- "+pnr); 
     } 
    } 
    public Collection<List<T>> permute(Collection<T> input) { 
     Collection<List<T>> output = new ArrayList<List<T>>(); 
     if (input.isEmpty()) { 
      output.add(new ArrayList<T>()); 
      return output; 
     } 
     List<T> list = new ArrayList<T>(input); 
     T head = list.get(0); 
     List<T> rest = list.subList(1, list.size()); 
     for (List<T> permutations : permute(rest)) { 
      List<List<T>> subLists = new ArrayList<List<T>>(); 
      for (int i = 0; i <= permutations.size(); i++) { 
       List<T> subList = new ArrayList<T>(); 
       subList.addAll(permutations); 
       subList.add(i, head); 
       subLists.add(subList); 
      } 
      output.addAll(subLists); 
     } 
     return output; 
    } 
} 

salida

P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]] 
P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]] 
P(3,1) : Count (3) :- [[3], [1], [2]] 
P(3,0) : Count (1) :- [[]] 

Mi problema es , a medida que voy aumentando los números en la lista de entrada. El tiempo de ejecución aumenta y después de 11 números en la lista de entrada, el programa casi muere. Toma alrededor de 2 GB de memoria para ejecutar.

Estoy ejecutando esto en una máquina que tiene 8 GB de RAM y procesador i5, por lo que la velocidad y el espacio no son un problema.

Agradecería, si alguien puede ayudarme a escribir un código más eficiente.

Answer 1

Si desea todas las permutaciones de 15-ish o más elementos, escríbalas en el disco o en una base de datos o algo así, ya que no caben en la memoria. Editar: Steinhaus–Johnson–Trotter algorithm. Esto es probablemente lo que estás buscando.

Answer 2

Usted se da cuenta de que está generando listas muy grandes, y que el tiempo de ejecución aumentará a medida que lo hace la longitud de la lista. ¿Has determinado por cuánto tiempo deben estar las listas que te están dando problemas?

Una cosa que podría ayudar a algunos sería imprimir cada permutación tal como la encuentras, en lugar de reunirlos todos en una lista y LUEGO imprimirlos. Por supuesto, si el objetivo es almacenar toda la lista, y no solo imprimirla, eso no ayudará.

Answer 3

Si no lo está almacenando, si solo está iterando a través de él, considere usar el algoritmo de Heap (n. ° 3 en http://www.cut-the-knot.org/do_you_know/AllPerm.shtml) o, para hacer la vida más fácil, use el Collections2.permutations de Guava, que en realidad no construye toda la lista de permutaciones, sino que las recorre sobre la marcha. (Revelación: Contribuyo a guayaba.)

Answer 4

biblioteca de Java de Google (guayaba) tiene un método de utilidad para esto: Collections2#permutations(Collection)