Question 2
Back to Exercise
Print all permutations of a string with distinct characters using recursion (choose each character as the first, permute the rest), and count them.
Solution
import java.util.ArrayList;
import java.util.List;
public class Main {
static void permute(String prefix, String rest, List<String> out) {
if (rest.isEmpty()) {
out.add(prefix);
return;
}
for (int i = 0; i < rest.length(); i++) {
permute(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1), out);
}
}
public static void main(String[] args) {
List<String> perms = new ArrayList<>();
permute("", "abc", perms);
System.out.println(perms + " " + perms.size());
perms.clear();
permute("", "java".replace("a", "").concat("A"), perms); // "jvA": 3 distinct letters
System.out.println(perms.size());
}
}
[abc, acb, bac, bca, cab, cba] 6 6
For n distinct characters there are n! permutations; each level of recursion fixes one more position.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!