Use recursion to find permutations of string using an iterator

Question

As the title implies, I'm having difficulty trying to recursively determine all the permutations of a given String. The catch is that String has to be given through a constructor of an object and then each of the permutations be found one by one. Basically, it has to work like this:

PermutationIterator iter = new PermutationIterator("eat");
while (iter.hasMorePermutations())
   System.out.println(iter.nextPermutation());

Here is the code that I'm using but doesn't seem to work and I don't know how to fix it.

public class PermutationIterator {

    private String word;
    private int pos;
    private PermutationIterator tailIterator;
    private String currentLetter;

    public PermutationIterator(String string) {
        word = string;
        pos = 0;
        currentLetter = string.charAt(pos) + "";
        if (string.length() > 1)
            tailIterator = new PermutationIterator(string.substring(pos + 1));
    }

    public String nextPermutation() {
        if (word.length() == 1) {
            pos++;
            return word;
        } else if (tailIterator.hasMorePermutations()) {
            return currentLetter + tailIterator.nextPermutation();
        } else {
            pos++;
            currentLetter = word.charAt(pos) + "";
            String tailString = word.substring(0, pos) + word.substring(pos + 1);
            tailIterator = new PermutationIterator(tailString);
            return currentLetter + tailIterator.nextPermutation();
        }

    }

    public boolean hasMorePermutations() {
        return pos <= word.length() - 1;
    }
}

Right now the program prints "eat" and "eta" but after that it through a StringIndexOutOfBounds error off of the second stack. Any help with solving this is much appreciated.

You forgot to mention that your code throws StringIndexOutOfBoundException....right? — ha9u63a7
– ha9u63a7, Commented Feb 12, 2015 at 21:21

sprinter · Accepted Answer · 2015-02-12 21:26:48Z

2

Rather than just supplying the fix let me help diagnose your issue and then you can have a go at fixing it.

If you look carefully at your code you'll see that the hasMorePermutations condition passes when pos == word.length() - 1. That means nextPermutation will be run when pos is pointing to the last character in the string. But in that case when the third branch executes you increment pos and then call word.substring(pos + 1). At that point pos + 1 will be larger than length of the string which will throw the exception.

I expect the fix will be fairly easy.

answered Feb 12, 2015 at 21:26

sprinter

28.1k8 gold badges51 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Kyefer Over a year ago

If I were to stop the .substring() call when pos == word.length() - 1 and everything below, what would I return instead? I had it surrounded by an if statement with hasMorePermutations() but I couldn't figure out the return because returning the original statement would cause a stack overflow.

sprinter Over a year ago

To be honest with you I think your technique of mimicking recursion with stacked iterators is overly complex. Unless you are expecting to use very long strings I would suggest just creating a list of all permutations in your constructor and then iterating through them in your methods. Much simpler and more obvious.

Kyefer Over a year ago

I'll probably just do that if I can't come up with a solution soon. In any case, this was for a class so I didn't decide to make it this way.

sprinter Over a year ago

@Kyefer Here's a hint on the fix: you don't need to append anything past pos to tailString when you are already at the end of the string - there's nothing there to append! Let me know if that doesn't make sense and I'll give you more direct help.

Dinesh Dontha · Accepted Answer · 2015-02-13 08:09:01Z

try this code - generates permutations for any given string

package testing;

import java.util.ArrayList;
import java.util.List;

public class Permutations {

	/*
	 * You will get n! (factorial) - permutations from this
	 * 
	 * Just like this Example: abc (3! = 6 permutations) [abc acb bac bca cab
	 * cbc]
	 */
	static String str = "abcd";
	static char[] ch = str.toCharArray();
	static List<String> s1 = new ArrayList<>();
	static List<String> s2 = new ArrayList<>();

	public static void main(String[] args) {

		// s1 - list stores initial character from the string
		s1.add(String.valueOf(ch[0]));

		// recursive loop - char by char
		for (int k = 1; k < ch.length; k++) {

			// adds char at index 0 for all elements of previous iteration
			appendBefore(s1, ch[k]);
			// adds char at last index for all elements of previous iteration
			appendAfter(s1, ch[k]);
			// adds char middle positins like a^b^C - if prev list stores
			// elements
			// whose size() is 3 - then it would have 2 positions fill
			/*
			 * say d is next char - d should be filled in _^_^_ _ positions are
			 * previous permuions for 3 chars a,b,c(i.e 6 permutations
			 */
			appendMiddle(s1, ch[k], k);
			// for every iteration first clear s1 - to copy s2, which contains
			// previous permutatons
			s1.clear();
			// now copy s2 to s1- then clear s2
			// - this way finally s2 contains all the permutations
			for (int x = 0; x < s2.size(); x++) {
				s1.add(s2.get(x));
			}
			System.out.println(s1);
			System.out.println(s1.size());
			s2.clear();
		}

	}

	private static void appendMiddle(List str, char ch, int positions) {

		for (int pos = 1; pos <= positions - 1; pos++) {
			for (int i = 0; i < str.size(); i++) {
				s2.add(str.get(i).toString().substring(0, pos) + String.valueOf(ch)
						+ str.get(i).toString().substring(pos, str.get(i).toString().length()));

			}
		}

	}

	private static void appendBefore(List str, char ch) {

		for (int i = 0; i < str.size(); i++) {
			s2.add(String.valueOf(ch) + str.get(i));

		}

	}

	private static void appendAfter(List str, char ch) {

		for (int i = 0; i < str.size(); i++) {
			s2.add(str.get(i) + String.valueOf(ch));

		}
	}

}

niese · Accepted Answer · 2015-05-15 13:44:43Z

0

do a little change in your hasMorePermutation method as below to solved StringIndexOutOfBounds exception.

public boolean hasMorePermutations()
{
    return pos < word.length() - 1;
}

answered May 15, 2015 at 13:44

niese

351 silver badge9 bronze badges

Collectives™ on Stack Overflow

Use recursion to find permutations of string using an iterator

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related