CODEWITHSUNDEEP
javastringarraylistpermutationrecurrence
iHowell
iHowell

Reputation: 2447

String Permutations

I was recently trying to write a script that print out all the permutations of a word in Java. For some reason it only prints out one. I just can't figure it out!

import java.util.*;

public class AllPermutations {

    ArrayList<String> letters = new ArrayList<String>();
    public void main(){
        letters.add("H");
        letters.add("a");
        letters.add("s");
        permutate("",letters);
    }

    public void permutate(String word, ArrayList<String> lettersLeft){
        if(lettersLeft.size()==0){
            System.out.println(word);
        }else{
            for(int i=0;i<lettersLeft.size();i++){
                String newWord = new String();
                newWord = word+lettersLeft.get(i);
                lettersLeft.remove(i);
                permutate(newWord, lettersLeft);
            }
        }
    }
}

Upvotes: 0

Views: 563

Answers (3)

Hitesh Garg
Hitesh Garg

Reputation: 1211

In this case you are removing the letters from the Arraylist and it gets empty till it reaches the end of first word.. Then after that list size is always zero...Add the removed letter back to the list...........

I would recommend you to use the below link and find good examples of String Permutations as there are both memory efficient and space efficient solutions of String permutations...

http://www.codingeek.com/java/strings/find-all-possible-permutations-of-string-using-recursive-method/

Upvotes: -1

Nabou
Nabou

Reputation: 549

The reason for that is lettersLeft is being passed by reference always. Once you are removing a letter from lettersLeft, it is being permanently removed. So for the first iteration you have "HAS" printed out. once that finishes, the recursion algorithm backs up a level to make the second iteration, but what do you know?? lettersLeft is empty. so it terminates without passing by the if statement causing it not to get another word or permutation. In order to resolve this, create a local copy, just like you did with newWord. Hope that helps.

Upvotes: 0

HeavenAgain
HeavenAgain

Reputation: 435

You need to add the letter you have removed back to the lettersLeft list

public void permutate(String word, ArrayList<String> lettersLeft){
    if(lettersLeft.size()==0){
        System.out.println(word);
    }else{
        for(int i=0;i<lettersLeft.size();i++){
            String temp = lettersLeft.remove(i);
            String  newWord = word+temp;
            permutate(newWord, lettersLeft);
            lettersLeft.add(i, temp);
        }
    }
}

I haven't tested it, but I think it should work.

The problem is that Java/you are passing by reference, not copy (ArrayList). Therefore once you reach the bottom of your recursion tree, lettersLeft will contain 0 elements, and once you go back up, it will still have 0 elements.

As a side note, StringBuilder/StringBuffer is better at doing string permutation task, since String is immutable, therefore you are wasting a lot of resource creating new Strings, n! to be exact. The difference between the two StringBuilder/Buffer is up to you to discover.

Upvotes: 3

Related Questions