Codice Java per permutazioni di un elenco di numeri

Question

Ho scritto un programma per trovare tutte le possibili permutazioni di un determinato elenco di elementi. Questo significa appunto che il mio programma stampe tutte le possibili P (n, r) i valori per r = 0 a n

Di seguito è riportato il codice:

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

uscita

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

Il mio problema è , mentre continuo ad aumentare i numeri nella lista di input. Il tempo di esecuzione aumenta e dopo 11 numeri nella lista di input, il programma quasi muore. Prende circa 2 GB di memoria per l'esecuzione.

L'ho eseguito su una macchina con 8 GB di RAM e processore i5, quindi la velocità e lo spazio non sono un problema.

Apprezzerei, se qualcuno può aiutarmi a scrivere un codice più efficiente.

Answer 1

Se si desidera tutte le permutazioni di 15-ish o più elementi, scriverli su disco o su un db o qualcosa del genere, poiché non si adatteranno alla memoria. Modifica: Steinhaus–Johnson–Trotter algorithm. Questo è probabilmente quello che stai cercando.

Answer 2

Ti rendi conto che stai generando elenchi molto grandi e che il tempo di esecuzione aumenterà con la lunghezza dell'elenco. Hai determinato quanto dovrebbero essere lunghe le liste che ti danno problemi?

Una cosa che potrebbe aiutare alcuni sarebbe quella di stampare ogni permutazione come la trovi, invece di raccoglierli tutti in un elenco e POI stamparli. Naturalmente, se il punto è quello di archiviare l'intera lista, e non solo stamparli, ciò non aiuterà.

Answer 3

Se non lo si sta memorizzando, se si sta semplicemente iterando attraverso di esso, quindi prendere in considerazione l'utilizzo dell'algoritmo di Heap (n. 3 su http://www.cut-the-knot.org/do_you_know/AllPerm.shtml) o, solo per semplificare la vita, utilizzare Collections2.permutations di Guava, che in realtà non costruisce l'intera lista di permutazioni - le attraversa al volo. (Disclosure: contribuisco a Guava.)

Answer 4

libreria Java di Google (Guava) ha un metodo di utilità per questo: Collections2#permutations(Collection)