Sort ArrayList in alphabetical order

Question

I am 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 the string "toys", I get:

toys tosy tyos tyso tsoy tsyo otys otsy oyts oyst osty 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 call your sort procedure from a recursive method that finds all permutations of your string before it is completely 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

Some comments already indicate that your recursive routine cannot sort on leaf nodes and expect to sort the entire list. You will have to return the accumulated rows in the collection, and then sort and print them once at the end.

More importantly, there is a good algorithm for rearranging an array in lexical order. It is used by the next_permutation library function in C ++ (which you can find for explanation), but it’s easy enough to translate it to java. You retrieve the char[] array, possibly with getCharArray , sort it with Arrays.sort and run it 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 he is doing, just run while(next_permutation(array)) {println(array);} and that’s all right. Note that this is very bad for arrays of more than 13 elements.

Answer 3

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

Answer 4

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 5

You can put all the permutations that you have already received and put them in a TreeSet or PriorityQueue that will put them in order. Then you will have to return them to your ArrayList.

Or you can use the Collections Sort , which sorts your ArrayList.

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