CODEWITHSUNDEEP
javastringalgorithmiterationpermutation
eyes enberg
eyes enberg

Reputation: 586

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

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!

Upvotes: 2

Views: 494

Answers (2)

prabodhprakash
prabodhprakash

Reputation: 3927

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

bacd

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.

Upvotes: 6

phflack
phflack

Reputation: 2727

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

Upvotes: 1

Related Questions