Permutation and Combination of a Given String

Description

Permutation and combination is very important topics in probablity, while many of the programming challenges also involved ability to generate all possible permtuation/combination for a given string. Hence, knowing how to write code to generate permutation and combination of a given string is essential.

Permutation

Permutation of string String str = "123".

Complexity

  • $O(n!)$
  • for string 123, first char has 3 choices, second char has 2 choices, etc
  • hence, there are $3 x 2 x 1 = 3!$ choices in total

Key Ideas

  • result of permutation has same length as the original string
  • fix one char at a time, recursively generate the rest (in circle)
  • which char to fix? here is an algorithm using swap to choose char for current char index.
1
2
3
4
5
6
s = "123" 
chossing char to fix for first character,

# swap s[0] w/ s[0] gives '123'
# swap s[0] w/ s[1] gives '213'
# swap s[0] w/ s[2] gives '321'
  • ex. fix first char (curr=1) could either be one of the 1,2,3. Hence, recursion tree spans into three nodes.
  • for fix second char (curr=2) with either 2,3. Since we only have two choices, hence, it spans into two nodes.
  • currentIdx == string.length() - 1 indicates the end of permutation and return

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class StringPermutation {
public static void main(String[] args) {
String string = "123";
permutate(string, 0);
}
public static void permutate(String string, int currentIdx) {
if (currentIdx == string.length() - 1) {
System.out.println(string);
}
for (int i = currentIdx; i < string.length(); i++) {
StringBuilder newString = new StringBuilder(string); // string immutable, use StringBuilder instead
char temp = newString.charAt(currentIdx);
newString.setCharAt(currentIdx, newString.charAt(i));
newString.setCharAt(i, temp);
permutate(newString.toString(), currentIdx+1);
}
}
}

ref: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Alternative approach for string permutation

  • instead of swapping, we can also add additional space boolean[] used to record character already been used
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// Arrays.sort(nums);
backtrack(new ArrayList<>(), result, nums, new boolean[nums.length]);
return result; // spot2: backtrack return here
}

public void backtrack(List<Integer> temp, List<List<Integer>> result, int[] nums, boolean[] visited) {
// if size == num.len, add to result
if (temp.size() == nums.length) {
result.add(new ArrayList<>(temp)); // important: new ArrayList, should not use temp (ref)
return;
}
for (int i = 0; i < nums.length; i++) { // spot1: backtrack return when i == nums.len
if (visited[i]) continue;
temp.add(nums[i]);
visited[i] = true;
backtrack(temp, result, nums, visited);
visited[i] = false; // draw this to see how element get removed
temp.remove(temp.size() - 1); // draw this to see how element get removed
}
}
}

https://leetcode.com/problems/permutations/description/

CS 106B Lecture: Backtracking (permute a string): https://www.youtube.com/watch?v=78t_yHuGg-0

Combination

Complexity

  • $O(2^n)$, where $n$ is the size of elements
  • for list of 1,2,3,4,5, where k = 3. for each of the element, it could either be choosen (1), or not choosen (0).
  • each element has two choices, where there are total n elemnts, hence, $O(2^n)$ total combinations
  • we need one more pass $O(2^n)$ to further eliminate invalid combinations, which its size is not k

Key Ideas

  • combination problem usually asks to select n from k, where n <= k.
  • similiarly to permutation, we could break big problem into smaller pieces.
  • fix first charactor, then recursively solve the rest (in circle).
  • which char to fix?

If a given string is s = "1234", where s.length() = 4, and k = 3. The only chars we could choose to fix is 1 and 2 since k = 3, which means we could not go beyond "2". Similary, the subproblem, w/ smaller size could be solved with the same logic, where result of combination locates at leave nodes.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.ArrayList;
import java.util.List;

public class StringCombination {
public static void main(String[] args) {
String string = "12345";
List<String> result = combination(3, string);
for (String str : result) {
System.out.println(str);
}
}

public static List<String> combination(int k, String string) {
int n = string.length();
List<String> result = new ArrayList<>();

if (k == 0) { // IMPORT: k = 0 when no more to select
result.add("");
return result;
}
// when k == n
if (k == n) {
result.add(string);
return result;
}

for (int i = 0; i < n-k+1; i++) {
char currentChar = string.charAt(i);
List<String> temp = combination(k-1, string.substring(i+1));
for (String tempStr : temp) {
result.add(currentChar + tempStr);
}
}
return result;
}
}

LeetCode77: Combinations https://leetcode.com/problems/combinations/description/

ref: https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

Alternative approach w/ backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 1ms version...
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combs = new ArrayList<List<Integer>>();
backtrack(combs, new ArrayList<Integer>(), 1, n, k);
return combs;
}

public static void backtrack(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
if(k==0) {
combs.add(new ArrayList<Integer>(comb));
return;
}

// n = 8, k = 5,
// for 1st element (k=5), i has to be <= 4, (5, 6, 7, 8 does not need to explore)
// for 2nd element (k=4), i has to be <= 5, (6, 7, 8 does not need to be explored)
// hence, when n = 100, k = 98, does not make sens to have [1, 10,11,12,13...] and find out it is not working
for(int i=start;i<=n-k+1;i++) { // IMPORT: n-k+1 is the key for speed up
comb.add(i);
backtrack(combs, comb, i+1, n, k-1);
comb.remove(comb.size()-1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 35ms version...
class Solution {
public List<List<Integer>> combine(int n, int k) {
if (n < k) return new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
backtrack(new ArrayList<>(), res, 1, k, n);
return res;
}

public static void backtrack(List<Integer> temp, List<List<Integer>> res, int startIdx, int k, int n) {
if (temp.size() == k) {
res.add(new ArrayList<>(temp));
return;
}

// select and backtrack
for (int i = startIdx; i <= n; i++) {
temp.add(i);
backtrack(temp, res, i + 1, k, n);
temp.remove(temp.size() - 1);
}
}
}

References

front cover ref: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

log

  • 05/12/2019: add combination 1ms version