10
\$\begingroup\$

Challenge:

Write a program which prints all the permutations of a string in alphabetical order.

Specifications:

Your program should accept a file as its first argument.
The file contains input strings, one per line.
Print the permutations of the string separated by commas, in alphabetical order.
We consider that digits < upper case letters < lower case letters.
The sorting should be performed in ascending order.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class PermutateString {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            System.out.println(
                permutateString(sortString(input.nextLine()))
            );
        }
        input.close();
    }

    private static void permutate(String prefix, String str, StringBuilder sb) {
        int len = str.length();

        if (len == 1) {
            sb.append(',').append(prefix).append(str);
        } else {
            for (int i = 0; i < len; i++) {
                permutate(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, len), sb);
            }
        }
    }

    private static String permutateString(String input) {
        StringBuilder characterBuilder = new StringBuilder();
        permutate("", input, characterBuilder);

        return characterBuilder.substring(1);
    }

    private static String sortString(String input) {
        char[] temp = input.toCharArray();
        Arrays.sort(temp);
        return String.valueOf(temp);
    }
}

Sample Input:

hat
abc
Zu6

Sample Output:

aht,ath,hat,hta,tah,tha
abc,acb,bac,bca,cab,cba
6Zu,6uZ,Z6u,Zu6,u6Z,uZ6

I first started solving this using a list of lists, but that required a lot of loops within loops and making size! lists seemed memory intensive..and confusing, This marks the first instance where I find a problem should be solved using recursion.

Generally wondering if there are any improvements I could make to solve this in a faster, cleaner, or memory efficient way.

For those interested, the source is CodeEval.com.

P.S. If it seems like Java 8 features were suggested before, yet not used here, there's a reason for that. I appreciate and take all feedback to heart it's just that CodeEval only uses Java 7. So, please don't think I'm intentionally disregarding the excellent advice I receive and nonetheless welcome.

\$\endgroup\$
4
\$\begingroup\$

Not much to comment on the permutation, but generally speaking you should use try-with-resources, Files.lines() and a healthy dose of Java 8 features for your main() method:

public static void main(String[] args) throws FileNotFoundException {
    try(Stream<String> lines = Files.lines(Paths.get(args[0]))) {
        lines.map(PermutateString::sortString)
                .map(PermutateString::permutateString)
                .forEach(System.out::println);
    } catch (IOException e) {
        // do something with this, e.g. show file not found message?
    }
}

Please check the use of Paths.get() for your case too...

\$\endgroup\$
0
\$\begingroup\$

Replace string builder with system out if you are expecting long words as memory usage is quickly increasing with word length and there is no further processing before sending it there anyway. Use the strategy pattern (interface) if you don't want your permutation code to reference complex system objects directly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.