Trier ArrayList par ordre alphabétique

Question

J'essaie de trouver toutes les permutations d'une chaîne et les classer par ordre alphabétique.

C'est ce que j'ai jusqu'à présent:

public class permutations { 

     public static void main(String args[]) { 
      Scanner s = new Scanner(System.in); 
      System.out.print("Enter String: "); 
      String chars = s.next(); 
      findPerms("", chars); 
     } 

     public static void findPerms(String mystr, String chars) { 

      List<String> permsList = new ArrayList<String>(); 

       if (chars.length() <= 1) 
         permsList.add(mystr + chars); 
         //System.out.print(mystr + chars + " "); 

       else 
         for (int i = 0; i < chars.length(); i++) { 
          String newString = chars.substring(0, i) + chars.substring(i + 1); 
          findPerms(mystr + chars.charAt(i), newString); 
         } 

       Collections.sort(permsList); 

       for(int i=0; i<permsList.size(); i++) { 
        System.out.print(permsList.get(i) + " "); 
       } 
     } 
} 

Si j'entre une chaîne "jouets" Je reçois:

jouets TOSY tyos tyso Tsoy TSYO OTYS otsy essais OYT oyst Osty osyt ytos YouTube Symphony Orchestra Yots Yost ysto ysot stoy styo soty soot syto syot

Qu'est-ce que je fais mal. Comment puis-je les obtenir dans l'ordre alphabétique? Merci!

Answer 1

Vous appelez votre routine de tri à partir de la méthode récursive qui trouve toutes les permutations de votre chaîne, avant qu'il ne soit Terminée

import java.util.*; 

public class permutations { 

     public static void main(String args[]) { 
      Scanner s = new Scanner(System.in); 
      System.out.print("Enter String: "); 
      String chars = s.next(); 
      List<String> myList = new ArrayList<String>(); 
      findPerms(myList, "", chars); 

      Collections.sort(myList); 

      for(int i=0; i<myList.size(); i++) { 
       System.out.print(myList.get(i) + " "); 
      } 

     } 

     public static void findPerms(List<String> permsList, String mystr, String chars) { 

      if (chars.length() <= 1) 
       permsList.add(mystr + chars);  
      else 
      for (int i = 0; i < chars.length(); i++) { 
       String newString = chars.substring(0, i) + chars.substring(i + 1); 
       findPerms(permsList, mystr + chars.charAt(i), newString); 
      } 

     } 
} 

Answer 2

Vous devez trier les résultats de l'appel de findperms, pas à l'intérieur l'appel recusif.

Answer 3

Check this out: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)

Answer 4

Vous pouvez mettre toutes les permutations que vous avez déjà acquis et les mettre dans un TreeSet ou PriorityQueue qui les mettre en ordre. Vous devrez alors les remettre dans votre ArrayList.

Ou vous pouvez utiliser un Collections Sort qui trie votre ArrayList.

Je recommande la dernière option. Here is an example si vous ne le comprenez pas.

Answer 5

Certains commentaires signalent déjà que votre routine récursive ne peut pas trier les nœuds feuilles et espérer trier la liste entière. Vous devez renvoyer les chaînes accumulées dans une collection, puis les trier et les imprimer une fois à la fin. Plus important encore, il existe un bon algorithme pour permuter un tableau dans l'ordre lexical. Il est utilisé par la fonction de bibliothèque next_permutation en C++ (que vous pouvez rechercher des explications), mais il est assez facile de traduire en java. Vous extrayez un tableau char[], peut-être avec getCharArray, triez-le avec Arrays.sort et exécutez-le jusqu'à ce qu'il renvoie false.

/** Helper function */ 
void reverse(char[] a, int f, int l) 
    { 
    while(l>f) 
    { 
    char tmp = a[l]; 
    a[l] = a[f]; 
    a[f] = tmp; 
    l--; f++; 
    } 
    } 

/** actual permutation function */ 
boolean next_permutation(char[] a) 
    { 
    if(a.length < 2) return false; 
    for(int i = a.length-1; i-->0;) 
    if(a[i] < a[i+1]) 
    { 
    int j=a.length-1; 
    while(!(a[i] < a[j])) 
     j--; 
    char tmp=a[i]; 
    a[i]=a[j]; 
    a[j]=tmp; 
    reverse(a, i+1, a.length-1); 
    return true; 
    } 
    reverse(a, 0, a.length-1); 
    return false; 
    } 

Une fois que vous comprenez ce qu'il fait, il suffit d'exécuter while(next_permutation(array)) {println(array);} et que vous faites bien. Notez que c'est très mauvais pour les tableaux de plus de 13 éléments.