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.

Answer 1

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()));
        }           
    }
}

Answer 2

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.

Answer 3

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.

Answer 4

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 ;) )