## All permutations of a string

Write a method to compute all permutations of a string.

My initial thoughts:

• Base case: the string is a single character, the only permutation is itself.
• Recursion: all permutations of size $n$ can be obtained by insert the first character $S[0]$ into all the possible positions of permutations of size $n-1$.

My initial codes:

```	public static Set<String> allPermutationsOfString(String s) {
if (s.length() == 1) {
Set<String> result = new HashSet<String>();
result.add(s);
return result;
} else {
Set<String> result = new HashSet<String>();
char c = s.charAt(0);
Set<String> subPermutations = allPermutationsOfString(s
.substring(1));
for (String permutation : subPermutations) {
// String newPermutation = new String();
for (int i = 0; i < permutation.length(); ++i) {
String newPermutation = permutation.substring(0, i) + c
+ permutation.substring(i);
result.add(newPermutation);
}
}
return result;
}
}

Comments after running:
It doesn’t work as expected.

INPUT: “abc”
EXPECTED OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba”
ACTUAL OUTPUT: “abc”, “bac”
CORRECTION: The highlighted line 13 should be revised to:
for (int i = 0; i <= permutation.length(); ++i) {

Solution:
public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) { // error case
return null;
} else if (s.length() == 0) { // base case
permutations.add("");
return permutations;
}
char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
permutations.add(insertCharAt(word, first, j));
}
}
return permutations;
}

public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}

Comments: exactly the same as mine except that it handles error case where string is null.

div.wpmrec2x{max-width:610px;}
div.wpmrec2x div.u > div{float:left;margin-right:10px;}
div.wpmrec2x div.u > div:nth-child(3n){margin-right:0px;}

Advertisements

(function(g,\$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);

var o = document.getElementById('crt-106126107');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-106126107",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-106126107'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

var o = document.getElementById('crt-1192890982');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1192890982",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1192890982'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

Like this:Like Loading...

Related
```