patternjavaMinor
Permutation of a string eliminating duplicates
Viewed 0 times
permutationstringduplicateseliminating
Problem
This code lists the permutations of the string, and eliminates duplicates if any. I'm looking for code review, best practices, optimizations etc.
I'm also verifying complexity: \$O(n! n)\$ as time complexity and \$O(n n)\$ as space complexity, where \$n\$ is length of the input string.
```
public final class Permutation {
private Permutation() {
};
/**
* Return permutation of a given string.
* But, if the string contains duplicate characters, it
* takes care to eradicate duplicate permutations.
*
* @param string the string whose permutation needs to be found out.
* @return a list with permuted values.
*/
public static List permutation(String string) {
final List stringPermutations = new ArrayList();
permute(string, 0, stringPermutations);
return stringPermutations;
}
private static void permute(String s, int currIndex, List stringPermutations) {
if (currIndex == s.length() - 1) {
stringPermutations.add(s);
return;
}
// prints the string without permuting characters from currIndex onwards.
permute(s, currIndex + 1, stringPermutations);
// prints the strings on permuting the characters from currIndex onwards.
for (int i = currIndex + 1; i < s.length(); i++) {
if (s.charAt(currIndex) == s.charAt(i)) continue;
s = swap(s, currIndex, i);
permute(s, currIndex + 1, stringPermutations);
}
}
private static String swap(String s, int i, int j) {
char[] ch = s.toCharArray();
char tmp = ch[i];
ch[i] = ch[j];
ch[j] = tmp;
return new String(ch);
}
public static void main(String[] args) {
for (String str : permutation("abc")) {
System.out.println(str);
}
System.out.println("------------");
for (String str : permutation("aabb")) {
System.out.println(str);
I'm also verifying complexity: \$O(n! n)\$ as time complexity and \$O(n n)\$ as space complexity, where \$n\$ is length of the input string.
```
public final class Permutation {
private Permutation() {
};
/**
* Return permutation of a given string.
* But, if the string contains duplicate characters, it
* takes care to eradicate duplicate permutations.
*
* @param string the string whose permutation needs to be found out.
* @return a list with permuted values.
*/
public static List permutation(String string) {
final List stringPermutations = new ArrayList();
permute(string, 0, stringPermutations);
return stringPermutations;
}
private static void permute(String s, int currIndex, List stringPermutations) {
if (currIndex == s.length() - 1) {
stringPermutations.add(s);
return;
}
// prints the string without permuting characters from currIndex onwards.
permute(s, currIndex + 1, stringPermutations);
// prints the strings on permuting the characters from currIndex onwards.
for (int i = currIndex + 1; i < s.length(); i++) {
if (s.charAt(currIndex) == s.charAt(i)) continue;
s = swap(s, currIndex, i);
permute(s, currIndex + 1, stringPermutations);
}
}
private static String swap(String s, int i, int j) {
char[] ch = s.toCharArray();
char tmp = ch[i];
ch[i] = ch[j];
ch[j] = tmp;
return new String(ch);
}
public static void main(String[] args) {
for (String str : permutation("abc")) {
System.out.println(str);
}
System.out.println("------------");
for (String str : permutation("aabb")) {
System.out.println(str);
Solution
- Best beginner's code I've seen. Possibly ever. Admittedly, I haven't reviewed too many beginner's programmes, but this one was definitely an easy review.
- Only style change I'd suggest is to avoid the single-line
if (s.charAt(currIndex) == s.charAt(i)) continue;. It's totally valid, but easy to miss. At least put thecontinueon a new line; many people prefer to put it in braces, too.
- Since your main() method is obviously a way to test the rest of the code, I'd suggest pulling the loops that are currently in there into a self-documenting method like
testPermutation(String arg)and call that frommain().
- Now that your main method is so simple (it just contains
testPermutation("abc");andtestPermutation("aabb");), change it to either
- loop over the arguments to main(), so you can call your program like
java yourpackage.Permutation abc aabb, or
- read strings from stdin until user exits.
- To measure time complexity, you can maintain a counter that gets incremented inside
swap(), and infer from that result. I think you'll find that it's much less than n! * n.
- Space complexity is the same as time complexity, since you create a new String every time you swap. Or depending on how you define "space complexity", I suppose it might be n * time complexity, since each time you swap, you create a String of length n.
Context
StackExchange Code Review Q#41618, answer score: 5
Revisions (0)
No revisions yet.