permutations of a string using iteration

im trying to find permutation of a given string but i want to use iteration. The recursive solution i found online and i do understand it but converting it to an iterative solution is really not working out. Below i have attached my code. i would really appreciate the help:

Code java:

---

public static void combString(String s) {
    char[] a = new char[s.length()];
    //String temp = "";
    for(int i = 0; i < s.length(); i++) {
        a[i] = s.charAt(i);
    }
    for(int i = 0; i < s.length(); i++) {
        String temp = "" + a[i];    
 
        for(int j = 0; j < s.length();j++) {
            //int k = j;
            if(i != j) {
                System.out.println(j);
                temp += s.substring(0,j) + s.substring(j+1,s.length());
            }               
        }
        System.out.println(temp);
    }
}

---

Could you please your code in [key] here enter your code [/key] in order to be more clear to everybody? :)

in order to work write code instead of key

Code :

---

 
public static void combString(String s) {
char[] a = new char[s.length()];
//String temp = "";
for(int i = 0; i < s.length(); i++) {
a[i] = s.charAt(i);
}
for(int i = 0; i < s.length(); i++) {
String temp = "" + a[i]; 
 
for(int j = 0; j < s.length();j++) {
//int k = j;
if(i != j) {
System.out.println(j);
temp += s.substring(0,j) + s.substring(j+1,s.length());
} 
}
System.out.println(temp);
}
}

---

Actually can you provide a small example.For example the word "Sam" what permutations does it have?I remember that the number of them is 2³,but i am not sure i know what the goal is.Sorry for my noobness :/

if u have a string "abc" then the output should be: abc, acb,bac,bca,cba,cab

So the formula was n! where n is the number of the letters of the word.So you have to output that many words.As for what should be changed,still thinking of it :)

Take a small sample like your abc char set. You have 3 characters. So you need to output 3 things:
All possible with a first...
All possible with b first...
All possible with c first...

Within a being first, you need to output all possible with b second, and all possible with c second.
Within b being first, you need to output all possible with a second, and all possible with c second.
Within c being first...........

recursion comes to mind
Edit.. ok I missed the part about iteration..

Ok,so i thought that if we let the letters of the words to be different among them,then we have to output n! permutations,where n is the number of the word's letters.So i also saw that given a string "abcd" with n=4 then it's permutations are the following

Code :

---

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

---

So i noticed that at 1st postition of the permutation every letter should appear (n-1)! times,at the 2nd position every letter(without the first included) should appear (n-2)! -in the set where the 1st's position letter remains the same-,at the 3rd position every letter(without the first two) should appear (n-3)! and at the 4rth position every letter(without the first three) should appear (n-4)!=(4-4)!=0!=1 times .So in general at m-th position every letter(without previous appearance of it) should appear (n-m)! times.
.
So this concept led me to a recursion code.But then i remember you wanted an iterative one.So i came around this code

Code :

---

public static void combString(String s) {
        int numberOfPermutations = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                for (int k = 0; k < s.length(); k++) {
                    for (int z = 0; z < s.length(); z++) {
                        if (i != j && j != k && i != k && i != z && j != z && k != z) {
                            System.out.format("%c%c%c%c%n", s.charAt(i), s.charAt(j),
                                    s.charAt(k), s.charAt(z));
                            numberOfPermutations++;
                        }
                    }
                }
            }
        }
        System.out.println(numberOfPermutations);
    }

---

The problem is that depending the number of letters of the word ,this code has to use the same number of for-loops(so the number of the letters is going to be equal with the number of the variables(with the counter for permutations not included.).This code is for a word with four letters and lets letters to appear as many times they found in the word,iterates of letters are enabled in other words.

The logic of the code is similar as you would do it in a piece of paper .The important thing is the if statement,which has this form because we do not want to permute a letter more than one time in every permutation.Try to remove this statement or some parts of it in order to get yourself convinced how this is need.

Quote:

---

Originally Posted by jps

recursion comes to mind

---

And that's better than the iterative one i provided.If you consider the complexity of what i wrote ,you will be dissapointed.

I'm a little surprised no one's posted a google/wikipedia answer yet.

Wikipedia - Generating Permutations in lexicographic order

A more efficient recursive answer is presented here:

Steinhaus-Johnson-Trotter algorithm

However he stated that he wants no recursive method :)

The first link isn't recursive.