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

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

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

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 :/

Re: permutations of a string using iteration

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

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

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..

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.

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.

Re: permutations of a string using iteration

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

Re: permutations of a string using iteration

However he stated that he wants no recursive method :)

Re: permutations of a string using iteration

The first link isn't recursive.