Efficient String Permutation Program.

The following piece of a code is a very efficient use of recursion to find the possible permutation of a string.


public class Permutations {

public static void perm1(String s) { perm1("", s); }

private static void perm1(String prefix, String s) {
int N = s.length();
if (N == 0)
System.out.println(prefix);
else {
for(int i = 0; i < N; i++){
perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
}
}
}
public static void main(String[] args) {
String alphabet = "Test";
String elements = alphabet.substring(0, alphabet.length());
perm1(elements);
}
}

Debugging this code might prove to be a little difficult though but excellent logic though.


Technorati Tags: , ,

18 comments:

blogger said...

this solution is very elegant and easy to understand.

Unknown said...

Woot! this is exactly what my group and i needed to do a project! thankyou, you are so awesome it isnt even funny.

you, mysteryman are my newfound hero!

TeamX

Anonymous said...

why de you use

public static void perm1(String s) { perm1("", s); }

??? it seems useless to me

and "private static" is so rare

Gunasekaran said...

Hey,This is great..Single line matters!!!!!!!!!!!!

Unknown said...

does not work for words with repeated letters like ass, less, lass, traffic, etc.
So some permutations are unneccessarily repeated. If fixed, ur code will be appreciated even more!

Unknown said...

>why de you use

>public static void perm1(String s) >{ perm1("", s); }

>??? it seems useless to me

That's encapsulation. By doing so you hide the detail of that implementation that requires a prefix.

private static is not that rare in singleton implementation because it reduces the needs to instantiate a class.

By the way, the solution is elegant.

grasshopper rtultatj said...

almost the seem solution in JavaScript
stringpermutation.js on GitHub

Anonymous said...

Very Nice and Simple Logic...
ThanQ for providing this......
.....Abhinav

Anonymous said...

Very Nice and Simple Logic...
ThanQ for providing this......
.....Abhinav

juchem said...

Efficient code using string concatenation in Java? I assume you're just aiming for a simple example of the general idea.

Anonymous said...

Thanks!! It was really simple to understand

Unknown said...

what is the complexity of this program

Anonymous said...

Complexity is O(n)= n^k

Anonymous said...

Great post!

Here's another great solution as well:

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

Anonymous said...

Great post!

I also found a great answer here as well:

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

Anonymous said...

Please Could You Make The Same For Permutation Of Numbers..

Rahul Jajodia said...

Dude Plzz Do The Same For Permutation Of Integer Values.
if there are 5 values then permutations till the first place shld be shown
eg:
942 is the number
permuations:
942
924
249
294
429
492
92
94
29
24
49
42
9
2
4



Please Do It...
I Am Gettting Stuck

Anonymous said...

Sir, I would like to have ur permission in using this code..
i ned this to do my project :PERMUTATION OF STRINGS IN GUI FORM:
thnks..