Code Java pour les permutations d'une liste de nombres
J'ai écrit un programme pour trouver toutes les permutations possibles d'une liste d'éléments. Cette précision signifie que mon programme affiche tous les possibles P(n,r) pour r=0 à n
Ci-dessous le code:
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;
}
}
Sortie
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) :- [[]]
Mon problème, c'est que je vais augmenter le nombre dans la liste d'entrée. Temps d'exécution augmente et après 11 numéros dans la liste de saisie, le programme meurt presque. Prend environ 2 GO de mémoire pour exécuter.
Je suis en cours d'exécution sur une machine ayant 8GO de RAM et processeur i5, de sorte que la vitesse et de l'espace n'est pas un problème.
Je vous serais reconnaissant, si quelqu'un peut m'aider à écrire un code plus efficace.
merci 🙂 je suis nouveau sur ce donc, ne pas avoir des idées où mettre quoi.
OriginalL'auteur dharam | 2012-05-08
Vous devez vous connecter pour publier un commentaire.
Si vous voulez toutes les permutations de 15-ish ou plusieurs éléments, de les écrire sur le disque ou un db ou quelque chose, puisqu'ils ne rentrent pas dans la mémoire.
Edit: Steinhaus–Johnson–Trotter de l'algorithme.
C'est probablement ce que vous cherchez.
Le lien est vraiment grand. Même l'accélération peut aider, je suppose. Merci pour le pointeur. Essayerai de le poster ici
+1 pour le lien, merci!
OriginalL'auteur Buhb
Si vous n'êtes pas stocker-si vous êtes juste de l'itération à travers elle-alors envisager l'utilisation de Segment de mémoire de l'algorithme (#3 sur http://www.cut-the-knot.org/do_you_know/AllPerm.shtml) -- ou, simplement pour rendre votre vie plus facile, utilisez la Goyave est
Collections2.permutations
, qui n'a pas de construire l'ensemble de la liste des permutations -- il se promène à travers eux à la volée. (Divulgation: je contribue à la Goyave.)OriginalL'auteur Louis Wasserman
Bibliothèque Java de Google (Goyave) a un utilitaire de méthode pour cela: Collections2#permutations(Collection)
OriginalL'auteur Kees van Dieren
Vous faire réaliser que vous êtes générer de très grandes listes, et que le temps d'exécution augmente à mesure que la longueur de la liste. Avez-vous déterminé combien de temps les listes qui sont en vous donnant la difficulté devrait être?
Une chose qui pourrait aider certains à imprimer chaque permutation que vous le trouverez, au lieu de les rassembler tous dans une liste, PUIS de les imprimer. Bien sûr, si le point est en effet de stocker l'ensemble de la liste, et non pas simplement de les imprimer, ce qui n'aidera pas.
OriginalL'auteur Scott Hunter