Permutations of a string

Question

public class Permute {
    public static void main(String[] args) throws IOException {
        System.out.println("Enter a string");
        BufferedReader bufReader = new BufferedReader(new InputStreamReader(System.in));
        String text = bufReader.readLine();
        shuffle("",text);
    }
    public static void shuffle(String dummy, String input){
        if(input.length() <= 1)
            System.out.println(dummy+input);
        else{
            for(int i=0; i <input.length();i++){
                input = input.substring(i,1) + input.substring(0,i) + input.substring(i+1);
                shuffle(dummy+input.substring(0,1),input.substring(1));
            }           
        }
    }
}

Am trying to print all the permutations of a string entered. And I really cannot guess where am going wrong because on paper I find that this executing. Where exactly am going wrong.

Did you try stepping through your code with a debugger to see where its behaviour diverged from what you expected? — Oliver Charlesworth, Feb 09 '11 at 20:31
How do you know you're going wrong? There might be a clue there ... — meriton, Feb 09 '11 at 20:36
Use variable for dummy+input.substring(0,1) and input.substring(1) and see if you can name them to match what they should be. — Joni, Feb 09 '11 at 20:36
@Chaitanya: Ok. So at some point, you should be able to see it do something unexpected... — Oliver Charlesworth, Feb 09 '11 at 20:45
@Oli: Thank you. I resolved the problem. It should be input.substring(i,i+1) instead of input.substring(i,1). Because each time I need only 1 character to reverse it, and I presumed substring to be substring(beginIndex, length). But it is substring(beginIndex,endIndex). Thank you for the help. — Chaitanya, Feb 09 '11 at 21:14

score 1 · Answer 1 · answered Feb 09 '11 at 21:43

Try change your shuffle:

public static void shuffle(String dummy, String input){
    if(input.length() <= 1)
        System.out.println(dummy+input);
    else{
        for(int i=0; i <input.length();i++){
           shuffle(dummy+input.charAt(i), input.substring(0, i) + input.substring(i+1, input.length()));
        }           
    }
}

score 1 · Answer 2 · answered Feb 10 '11 at 06:13

public class Permute {
    public static void main(String[] args) throws IOException {
        System.out.println("Enter a string");
        BufferedReader bufReader = new BufferedReader(new InputStreamReader(System.in));
        String text = bufReader.readLine();
        shuffle("",text);
    }
    public static void shuffle(String dummy, String input){
        if(input.length() <= 1)
            System.out.println(dummy+input);
        else{
            for(int i=0; i <input.length();i++){
                input = input.substring(i,i+1) + input.substring(0,i) + input.substring(i+1);
                shuffle(dummy+input.substring(0,1),input.substring(1));
            }           
        }
    }
}

It should be input.substring(i,i+1) instead of input.substring(i,1). Because each time I need only 1 character to be constant, which is at the beginning of the string and others have to be jumbled.

The bug was I presumed the functionality of substring to be substring(beginIndex, length). But it is substring(beginIndex,endIndex).

@Oli: Thank you for the help.

score 0 · Answer 3 · answered Feb 09 '11 at 20:42

0

Since this seems like a homework assignment I once did I will help you out here. You will need two loops, one inside the other.

for(int i;i<something;i++)  
    for(int j;j<somethingElse;j++)

This will enable you to generate the permutations that are required.

answered Feb 09 '11 at 20:42

Woot4Moo

23,987
16
94
151

It doesn't need to be recursive according to the OP. Also, any recursive solution can be unrolled into an iterative version. furthermore the OP is struggling to see where the issue is. – Woot4Moo Feb 09 '11 at 20:52
1

Suggesting an entirely different structure (without any specifics at all) is not really very helpful! – Oliver Charlesworth Feb 09 '11 at 21:00
@Oli for a student they must understand iteration before they can understand recursion. That is my 2 cents at least. Also why would I give a full answer for a homework assignment? – Woot4Moo Feb 09 '11 at 21:11
1

There's quite a gap between giving a full solution and giving no details at all. The OP is trying to debug his/her recursive approach; how is your answer helping with that? – Oliver Charlesworth Feb 09 '11 at 21:13

score 0 · Answer 4 · answered Feb 09 '11 at 21:22

Replace two lines in the for loop with following:

 String partString = input.substring(0, i) + input.substring(i + 1);
 shuffle(dummy + input.charAt(i), partString);

Since this looks like your homework I will let you figure out. If not, will post explanation after a bit ( got to get back to my day job ;) )

Permutations of a string

4 Answers4

Linked