0

I'm trying to permute a String and copy all the permutations into an ArrayList. But I'm getting an infinite loop, and I fail to see where. Any help?

private static List<String> permute(String str) {
    List<String> permutations = new ArrayList<String>();
    return permuteHelper("", str, permutations);
}

private static List<String> permuteHelper(String prefix, String str, List<String> permutations) {
    int length = str.length();

    if (length == 0) {
        permutations.add(prefix);
    } else {
        for (int i = 0; i < length; i++) {
            permuteHelper(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, length), permutations);
        }
    }
    return permutations;
}
Tom
  • 16,842
  • 17
  • 45
  • 54
Adway Dhillon
  • 77
  • 1
  • 4
  • 16
  • possible duplicate of [Generating all permutations of a given string](http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) – Teo Jan 01 '15 at 21:55
  • 1
    Why `permuteHelper` is returning a `List`? Since this method comes from http://stackoverflow.com/a/4240323/1587046, you could let it as the same and only add the String to the list when the length is 0 (as you did). Then permute just have to return permutation after the call to permuteHelper. – Alexis C. Jan 01 '15 at 21:57
  • Because I want to return a List of all possible permutations. – Adway Dhillon Jan 01 '15 at 22:05
  • 1
    @AdwayDhillon And? I don't see your point. Well usea debugger to correct your program. – Alexis C. Jan 01 '15 at 22:17
  • 1
    There is no need to return the list, since you're not changing the reference of the passed permutations list. But your code works, it just needs a lot of time for longer Strings. – Tom Jan 01 '15 at 22:47
  • @AdwayDhillon just do some math, for a String with 20 characters, it will have 20! or 2.432902e+18 permutations. Assuming that you are running a computer which can do 10^9 operations per second, so the time needed is 2432902008.18 seconds or around 28158 days!! – Pham Trung Jan 02 '15 at 03:04
  • @PhamTrung yeah I was thinking of the same thing, but this seems to be the easiest way to permute a string. Or is there another way which takes less time? – Adway Dhillon Jan 02 '15 at 04:58
  • Have you tested this with short strings? It's possible that you are interpreting very long run time as an infinite loop. – sprinter Jan 02 '15 at 05:33
  • @sprinter yeah I did check it with shorter strings. It still doesnt work. – Adway Dhillon Jan 02 '15 at 05:35
  • @AdwayDhillon uhm, just to list all permutations will take that amount of time, so even if it exists an algo which is faster than yours, it will still not make any difference. However, You can improve your algo by generating those permutations based on number of different characters, which can reduce the amount of repetitive work, and you can make use of a StringBuilder instead of String concatenation, but as I said, this will not help much :). – Pham Trung Jan 02 '15 at 05:37

0 Answers0