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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
---
id: complete-rec
title: "Complete Search with Recursion"
author: Darren Yao, Sam Zhang
description: "Includes generating subsets and permutations."
frequency: 2
prerequisites:
- intro-complete
---
import { Problem } from "../models";
export const problems = {
subset: [
new Problem("CSES", "Apple Division", "1623", "Intro|Very Easy", false, ["Recursion", "Subsets"], "all $2^n$ subsets"),
],
permSam: [
new Problem("CSES", "Creating Strings I", "1622", "Intro|Easy", false, [], "all perms of string"),
],
ex: [
new Problem("Bronze", "Photoshoot", "988", "Normal", false, [], ""),
],
back: [
new Problem("CSES", "Chessboard and Queens", "1624", "Normal", false, [], "Recursively backtrack. See CSES book for more details."),
new Problem("CSES", "Grid Paths", "1625", "Insane", false, [], "Recursively backtrack. See CSES book for more details."),
],
gen: [
new Problem("Bronze", "Back & Forth", "857", "Hard", false, [], "exponential time going through all possibilities"), // 99.63
new Problem("Bronze", "Livestock Lineup", "965", "Hard", false, ["permutations"], ""), // 91.95
],
};
## Generating Subsets
<Resources>
<Resource source="CPH" title="5.1 - Generating Subsets" starred> </Resource>
</Resources>
<Problems problems={problems.subset} />
## Generating Permutations
<Resources>
<Resource source="CPH" title="5.2 - Generating Permutations" starred> </Resource>
</Resources>
<Problems problems={problems.permSam} />
<br />
A **permutation** is a reordering of a list of elements. Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if $N \leq 10$, we can probably iterate through all permutations and check each permutation for validity. For a list of $N$ elements, there are $N!$ ways to permute them, and generally we'll need to read through each permutation once to check its validity, for a time complexity of $O(N \cdot N!)$.
<Resources>
<Resource source="GFG" url="write-a-c-program-to-print-all-permutations-of-a-given-string" title="Printing all Permutations of Given String"> </Resource>
</Resources>
### Lexicographical Order
This term is mentioned quite frequently:
<Problems problems={problems.ex} />
Think about how are words ordered in a dictionary. (In fact, this is where the term "lexicographical" comes from.)
In dictionaries, you will see that words beginning with the letter 'a' appears at the very beginning, followed by words beginning with 'b', and so on. If two words have the same starting letter, the second letter is used to compare them; if both the first and second letters are the same, then use the third letter to compare them, and so on until we either reach a letter that is different, or we reach the end of some word (in this case, the shorter word goes first).
Permutations can be placed into lexicographical order in almost the same way. We first group permutations by their first element; if the first element of two permutations are equal, then we compare them by the second element; if the second element is also equal, then we compare by the third element, and so on.
For example, the permutations of 3 elements, in lexicographical order, are
$$
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
$$
Notice that the list starts with permutations beginning with 1 (just like a dictionary that starts with words beginning with 'a'), followed by those beginning with 2 and those beginning with 3. Within the same starting element, the second element is used to make comparisions.
Generally, unless you are specifically asked to find the lexicographically smallest/largest solution, you do not need to worry about whether permutations are being generated in lexicographical order. However, the idea of lexicographical order does appear quite often in programming contest problems, and in a variety of contexts, so it is strongly recommended that you familiarize yourself with its definition.
### Checking Permutations in Lexicographical Order
What's going to be in the `check` function depends on the problem, but it should verify whether the current permutation satisfies the constraints given in the problem.
<LanguageSection>
<CPPSection>
#### Method 1
($O(N\cdot N!)$ code)
<IncompleteSection />
#### Method 2
<Resources>
<Resource source="Mark Nelson" title="Next Permutation" url="https://marknelson.us/posts/2002/03/01/next-permutation.html"> </Resource>
</Resources>
Alternatively, we can just use the [`next_permutation()`](https://en.cppreference.com/w/cpp/algorithm/next_permutation) function. This function takes in a range and modifies it to the next greater permutation. If there is no greater permutation, it returns false. To iterate through all permutations, place it inside a `do-while` loop. We are using a `do-while` loop here instead of a typical `while` loop because a `while` loop would modify the smallest permutation before we got a chance to process it.
```cpp
do {
check(v); // process or check the current permutation for validity
} while(next_permutation(v.begin(), v.end()));
```
Each call to `next_permutation` makes a constant number of swaps on average if we go through all $N!$ permutations of size $N$.
</CPPSection>
<JavaSection>
```java
import java.util.*;
public class Test {
static boolean[] used;
static ArrayList<Integer> cur = new ArrayList<Integer>();
static int n;
static void gen() {
if (cur.size() == n) {
check(cur); // check current permutation for validity, or print it, etc.
return;
}
for (int i = 0; i < n; ++i) if (!used[i]) {
used[i] = true; cur.add(i+1);
gen();
used[i] = false; cur.remove(cur.size()-1);
}
}
static void genPerm(int _n) {
n = _n; used = new boolean[n];
gen();
}
public static void main(String[] Args) {
genPerm(5);
}
}
```
</JavaSection>
</LanguageSection>
## Backtracking
<Problems problems={problems.back} />
<Resources>
<Resource source="CPH" title="5.3, 5.4 - Backtracking, Pruning"> </Resource>
</Resources>
No (current) bronze problem should require pruning ...
## Problems
<Problems problems={problems.gen} />
<IncompleteSection />
|
