Sort ArrayList alphabetically

Question

I'm trying to find all permutations of a string and sort them alphabetically.

This is what I have so far:

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) + " ");
               }
       }
}

IF I enter a string "toys" I get:

toys tosy tyos tyso tsoy tsyo otys otsy oyts oyst osty osyt ytos ytso yots yost ysto ysot stoy styo soty soyt syto syot

What am I doing wrong. How can I get them in alphabetical order? Thanks!

Answer 1

You're calling your sort routine from within the recursive method that finds all permutations of your String, before it's been fully populated

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

You need to sort the results of the call of findperms, not inside the recusive call.

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

You could put all the permutations that you have already gotten and put them in a TreeSet or PriorityQueue which will put them in order. You would then have to put them back into your ArrayList.

Or you could use a Collections Sort which sorts your ArrayList.

I recommend the last option. Here is an example if you do not understand it.

Answer 5

Some of the comments already point out that your recursive routine can't do a sort at the leaf nodes and expect to sort the whole list. You'd have to return the accumulated strings in a collection and then sort and print them once at the end.

More importantly, there is a nice algorithm for permuting an array in lexical order. It's used by the next_permutation library function in C++ (which you can look up for explanations), but it's easy enough to translate to java. You extract a char[] array, maybe with getCharArray, sort it with Arrays.sort and run this until it returns 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; 
  }

Once you understand what it does, just run while(next_permutation(array)) {println(array);} and you're doing fine. Note that this is very bad for arrays over 13 or so elements.