# permutations of a string using iteration

• August 11th, 2012, 08:17 AM
ueg1990
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); } }```
• August 11th, 2012, 08:23 AM
Samaras
Re: permutations of a string using iteration
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
• August 11th, 2012, 08:31 AM
ueg1990
Re: permutations of a string using iteration
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); } }```
• August 11th, 2012, 08:45 AM
Samaras
Re: permutations of a string using iteration
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 :/
• August 11th, 2012, 08:49 AM
ueg1990
Re: permutations of a string using iteration
if u have a string "abc" then the output should be: abc, acb,bac,bca,cba,cab
• August 11th, 2012, 08:56 AM
Samaras
Re: permutations of a string using iteration
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 :)
• August 11th, 2012, 09:55 AM
jps
Re: permutations of a string using iteration
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..
• August 11th, 2012, 10:23 AM
Samaras
Re: permutations of a string using 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.
• August 11th, 2012, 10:26 AM
Samaras
Re: permutations of a string using iteration
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.
• August 11th, 2012, 12:02 PM
helloworld922
Re: permutations of a string using iteration

Wikipedia - Generating Permutations in lexicographic order

A more efficient recursive answer is presented here:

Steinhaus-Johnson-Trotter algorithm
• August 11th, 2012, 02:20 PM
Samaras
Re: permutations of a string using iteration
However he stated that he wants no recursive method :)
• August 11th, 2012, 03:23 PM
helloworld922
Re: permutations of a string using iteration