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!
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);
}
}
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With