How to compute all the possible permutations given the characters of a given string?

Question

I have written this code to find the possible permutation of string using iterative approach, but it's giving wrong output as follows. Please advise, what's wrong in the code?
Output I'm getting:

BCAABC ACBABC ABCABC

Expetced output is :

ABC ACB BAC BCA CBA CAB

 public class PrintPermutation {

     public static void main(String[] args) throws Exception {

         String str = "ABC";
         String permutation = str + "";

         if (str.length() == 0) {
             System.out.println("String length is zero and can't make the permutation");
             return;
         }

         for (int i = 0; i < str.length(); i++) 
         {

             char ch = str.charAt(i);
             String left = str.substring(0, i);
             String right = str.substring(i + 1);

             String Merge = left + right;

             System.out.println(Merge+ch+permutation);

         }
     }
 }

Why you concat `str` with an empty string? Take care of javav naming conventions. variable names should start with lower case character — Jens, Aug 29 '22 at 06:14
Now is a good time to learn how to debug. It is very helpfull if you have such issues — Jens, Aug 29 '22 at 06:15
it also looks like you are trying to imitate a recursive function but using iterative method. — Tan Yu Hau Sean, Aug 29 '22 at 06:15
@Tan Yu Hau Sean, it would be great, if you could help me to fix the code and post it as answer? Thank you. :) — Ganesh Kulkarni, Aug 29 '22 at 06:15
It is not clear what your want as an output. You want all possible permutations? Please update your question and be more concrete. — yezper, Aug 29 '22 at 06:16
Tan Yu Hau Sean, No, I'm trying out different approach and this tutorial link is different. — Ganesh Kulkarni, Aug 29 '22 at 06:20
[This one](https://www.geeksforgeeks.org/print-all-permutations-of-a-string-in-java/) is the closest I can find that is similar to your code. — Tan Yu Hau Sean, Aug 29 '22 at 06:21
This is the output which I'm getting, which I have already mentioned in the question. — Ganesh Kulkarni, Aug 29 '22 at 06:21
Because your question was unclear. A clear and concise way to ask your question would have been: `How to compute all the possible permutations given the characters of a given string?` — yezper, Aug 29 '22 at 06:37
yezper, updated :), I did mention everything in the description though. — Ganesh Kulkarni, Aug 29 '22 at 06:39
alright, [this](https://stackoverflow.com/a/14444037/10671013) is a link that shows how to permutate an array if you are interested. I came across it as I was trying to emulate the method shown on this [link](https://www.geeksforgeeks.org/permutations-string-using-iteration/) in your case. So, what you could do if you arent interested in earlier links, is to treat your string as a char array and permutate the array. — Tan Yu Hau Sean, Aug 29 '22 at 07:16
Tan Yu Hau Sean, thank you, now it make sence. Acually I was asked this, question in interview, to print it iteratively, That's why I'm trying to achive it,recursive approach is easy. I did check : Johnson and Trotter algorithm as well. — Ganesh Kulkarni, Aug 29 '22 at 07:26
then you could check this out. its one of the few iterative solutions i could find. everything else uses recursion somewhere https://www.techiedelight.com/find-permutations-string-cpp-java-iterative/ — Tan Yu Hau Sean, Aug 29 '22 at 09:01

score 1 · Answer 1 · answered Aug 29 '22 at 09:41

This is a solution I found online. This one is interesting, because rather than using recursion or some complex iterative algorithm, they make the solution simpler by using some mathematical understanding. link here

public static void permutateString2(String s){
        int len = s.length();
        int factorial = factorial(s.length());

        for (int i=0; i<factorial; i++){
            String str = s;
            int counter = 0;
            StringBuilder permutation = new StringBuilder();

            while (counter < len){
                
                int idx = i % (len - counter);
                
                permutation.append(str.charAt(idx));
                
                if (idx == 0){
                    str = str.substring(idx+1);
                }else if (idx == str.length()-1){
                    str = str.substring(0, str.length()-1);
                }else{
                    str = str.substring(0, idx) + str.substring(idx+1, str.length());
                }
                
                counter++;
            }
            System.out.println(permutation.toString());
        }
    }

    private static int factorial(int n){
        int result = 1;
        for (int i=1; i<= n; i++){
            result *= i;
        }
        return result;
    }

I just noticed that the link also provides some source code, but because I just stumbled through their logic/pseudocode, so mine may seem janky — Tan Yu Hau Sean, Aug 29 '22 at 09:42

How to compute all the possible permutations given the characters of a given string?

1 Answers1