Can't produce all permutations of a String (iteratively)

Question

So I'm working on some Java exercises, and one that has caught my attention recently is trying to produce all permutations of a String using iteration. There are plenty of examples online - however, a lot of them seem very complex and I'm not able to follow.

I have tried using my own method, which when tested with a string of length 3 it works fine. The method is to (for each letter) keep moving a letter along the string, swapping it with whatever letter is in front of it. E.g.

index:  012
string: abc 

(iteration 1) swap 'a' (index 0) with letter after it 'b' (index 0+1) : bac
(iteration 2) swap 'a' (index 1) with letter after it 'c' (index 1+1) : bca
(iteration 3) swap 'a' (index 2) with letter after it 'b' (index 0)   : acb
current permutations: abc (original), bac, bca, acb

(iteration 3) swap 'b' (index 1) with letter after it 'c' (index 1+1) : acb
(iteration 4) swap 'b' (index 2) with letter after it 'a' (index 0)   : bca
(iteration 5) swap 'b' (index 0) with letter after it 'c' (index 1)   : cba
current permutations: abc (original), bac, bca, acb, acb, cba

...

This is how I implemented it in Java:

String str = "abc"; // string to permute
char[] letters = str.toCharArray(); // split string into char array
int setLength = factorial(letters.length); // amount of permutations = n!
HashSet<String> permutations = new HashSet<String>(); // store permutations in Set to avoid duplicates
permutations.add(str); // add original string to set

// algorithm as described above
for (int i = 0; i < setLength; i++) {
    for (int j = 0; j < letters.length; j++) {
        int k;
        if (j == letters.length - 1) {
            k = 0;
        } else {
            k = j + 1;
        }
        letters = swap(letters, j, k);
        String perm = new String(letters);
        permutations.add(perm);
    }
}

The problem is if I input a string of length 4, I only end up with 12 permutations (4x3) - if I input a string of length 5, I only end up with 20 permutations (5x4).

Is there a simple modification I could make to this algorithm to get every possible permutation? Or does this particular method only work for strings of length 3?

Appreciate any feedback!

I'm not sure there's an easy way to do it with your methods, but more likely you lucked out on size 3 strings. What I would recommend for solving this is creating a tree of some sort, a trie that contains all possibilities — phflack, Jan 27 '16 at 15:45
Iteration tends to be the best solution in Java, however when the number of loops you would need is proportional to the problem, recursion is most likely the best solution. While in theory, you can turn any recursive method into a loop using your own stack, this is usually pretty complicated and at a minimum I suggest you implement it recursively before attempting this. — Peter Lawrey, Jan 27 '16 at 15:45
Have a look at their algo http://www.programcreek.com/2014/06/leetcode-next-permutation-java/ — serhiyb, Jan 27 '16 at 15:47
Can you provide your entire Java code, along with the other two functions, would be easier to execute. — prabodhprakash, Jan 27 '16 at 15:52

score 6 · Answer 1 · edited May 23 '17 at 12:08

Suppose the input is "abcd". This is how your algorithm will work

bacd

bcad

bcda

If you observe carefully, "a" was getting positioned at all indexes and the following consecutive letter was getting replaced with "a". However, after your algorithm has produced "bacd" - it should be followed by "badc" also, which will be missing from your output.

For string of length 4, When you calculated the number of permutations as factorial, you understand that the first position can be occupied by 4 characters, followed by 3, 2 and 1. However, in your case when the first two positions are occupied by "ba" there are two possibilities for 3rd position, i.e. c and d. While your algorithm correctly finds "cd", it fails to find "dc" - because, the loop does not break the problem into further subproblems, i.e. "cd" has two permutations, respectively "cd" and "dc".

Thus, the difference in count of your permutations and actual answer will increase as the length of string increases.

To easily break problems into sub-problem and solve it, many algorithm uses recursion.

However, you could look into Generate list of all possible permutations of a string for good iterative answers.

Also, as the length of string grows, calculating number of permutation is not advisable.

new answer, found it very useful – Kiran Kumar Jan 28 '16 at 08:03 — Kiran Kumar, Jan 28 '16 at 08:03

phflack · Answer 2 · 2016-01-27T16:07:34.060

While I do not know of a way to expand upon your current method of switching places (I've attempted this before to no luck), I do know of a fairly straightforward method of going about it

//simple method to set up permutate
private static void permutations(String s)
{
  permutate(s, "");
}

//takes the string of chars to swap around (s) and the base of the string to add to
private static void permutate(String s, String base)
{
  //nothing left to swap, just print out
  if(s.length() <= 1)
    System.out.println(base + s);
  else
    //loop through the string of chars to flip around
    for(int i = 0; i < s.length(); i++)
      //call with a smaller string of chars to flip (not including selected char), add selected char to base
      permutate(s.substring(0, i) + s.substring(i + 1), base + s.charAt(i));
}

The goal with this recursion is to delegate as much processing as possible to something else, breaking the problem down bit by bit. It's easy to break down this problem by choosing a char to be first, then telling a function to figure out the rest. This can then be done for each char until they've all been chosen once

Can't produce all permutations of a String (iteratively)

2 Answers2