Table of Contents
SubsetsResourcesSolution - Apple DivisionGenerating Subsets RecursivelyGenerating Subsets with BitmasksPermutationsLexicographical OrderSolution - Creating Strings IGenerating Permutations RecursivelyGenerating Permutations Using next_permutationBacktrackingResourcesSolution - Chessboard & QueensUsing next_permutationUsing BacktrackingPruningProblemsComplete Search with Recursion
Author: Many
Contributors: Darren Yao, Sam Zhang, Michael Cao, Andrew Wang, Benjamin Qi, Dong Liu, Maggie Liu, Dustin Miao
Includes generating subsets and permutations.
Prerequisites
Table of Contents
SubsetsResourcesSolution - Apple DivisionGenerating Subsets RecursivelyGenerating Subsets with BitmasksPermutationsLexicographical OrderSolution - Creating Strings IGenerating Permutations RecursivelyGenerating Permutations Using next_permutationBacktrackingResourcesSolution - Chessboard & QueensUsing next_permutationUsing BacktrackingPruningProblemsWarning!
Although knowledge of recursion is not strictly necessary for Bronze, we think that it makes more sense to include this module as part of Bronze rather than Silver.
Subsets
Focus Problem – read through this problem before continuing!
Resources
Resources | ||||
---|---|---|---|---|
CPH | good explanation + code, no need to repeat |
Solution - Apple Division
Since , we can solve the focus problem by trying all possible divisions of apples into two sets and finding the one with the minimum difference in weights. Here are two ways to do this.
Generating Subsets Recursively
The first method would be to write a recursive function which searches over all possibilities.
At some index, we either add to the first set or the second set, storing two sums and with the sum of values in each set.
Then, we return the difference between the two sums once we've reached the end of the array.
C++
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;#define pb push_back#define rsz resize#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()using pi = pair<int,int>;#define f first
Java
import java.util.*;import java.io.*;public class Main {static int N;static int weights[];public static void main(String[] args) throws Exception {Kattio io = new Kattio();
Python
n = int(input())p = list(map(int, input().split()))def solve(i, s1, s2):if i == n:return abs(s2 - s1)return min(solve(i + 1, s1 + p[i], s2),solve(i + 1, s1, s2 + p[i]))print(solve(0, 0, 0))
Generating Subsets with Bitmasks
Warning!
You are not expected to know this for Bronze.
A bitmask is an integer whose binary representation is used to represent a subset. For a particular bitmask, if the 'th bit is turned on (equal to ), we say the 'th apple is in . Then, the rest of the apples are in . We can iterate through all subsets if we check all bitmasks ranging from to . For each bitmask, find the sum of and and find the minimum difference between their sums.
Note the fancy bitwise operations:
1 << x
for an integer is another way of writing , which, in binary, has only the 'th bit turned on.- The
&
(and) operator will take two integers and return a new integer.a & b
for integers and will return a new integer whose 'th bit is turned on if and only if the 'th bit is turned on for both and . Thus,mask & (1 << x)
will return a positive value only if the 'th bit is turned on in .
Bitwise Operations
Check this module for more information.
C++
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;#define pb push_back#define rsz resize#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()using pi = pair<int,int>;#define f first
Java
import java.util.*;import java.io.*;public class Main {public static void main(String[] args) throws Exception {Kattio io = new Kattio();int N = io.nextInt();int weights[] = new int[N];for (int i = 0; i < N; i++) {
Python
n = int(input())p = list(map(int, input().split()))ans = float('inf')for mask in range(1 << n):s1, s2 = 0, 0for i in range(n):if mask & (1 << i):s1 += p[i]else:s2 += p[i]ans = min(ans, abs(s1 - s2))print(ans)
Permutations
A permutation is a reordering of a list of elements.
Focus Problem – read through this problem before continuing!
Lexicographical Order
This term is mentioned quite frequently, ex. in USACO Bronze - Photoshoot.
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
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.
Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if , we can just iterate through all permutations and check each permutation for validity.
Solution - Creating Strings I
Resources | ||||
---|---|---|---|---|
CPH | brief explanation + code for both of the methods below |
Generating Permutations Recursively
Just a slight modification of method 1 from CPH.
We'll use the recursive function to find all the permutations of the string . First, keep track of how many of each character there are in . For each function call, add an available character to the current string, and call with that string. When the current string has the same size as , we've found a permutation and can add it to the list of .
C++
#include <iostream>#include <vector>#include <algorithm>using namespace std;string s;vector<string> perms;int char_count[26];void search(string curr)
Java
import java.io.*;import java.util.*;public class CreatingStrings1{static String s;static List<String> perms = new ArrayList<String>();static int[] charCount = new int[26];static void search(String curr)
Python
s = input()perms = []char_count = [0] * 26def search(curr):# we've finished creating a permutationif len(curr) == len(s):perms.append(curr)returnfor i in range(26):
C++
next_permutation
Generating Permutations Using Resources | ||||
---|---|---|---|---|
Mark Nelson | explanation with an example |
Alternatively, we can just use the 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.
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.
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 permutations of size .
Warning!
One small detail is that you need to sort the string before calling
next_permutation()
because the method generates strings in lexicographical
order. If the string isn't sorted, then strings which are lexicographically
smaller than the initial string won't be generated.
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){string s;cin >> s;vector<string> perms;
Python
itertools.permutations
Generating Permutations Using Since itertools.permutations
treats elements as unique based on position, not
value, it returns all permutations, with repeats. Putting the returned tuples in
a set can filter out duplicates, and since tuples are returned, we need to join
the characters into a string.
import itertoolss = input()# perms is a sorted list of all the permutations of the given stringperms = sorted(set(itertools.permutations(s)))print(len(perms))for perm in perms:print("".join(perm))
Java
Backtracking
Focus Problem – read through this problem before continuing!
Resources
Resources | ||||
---|---|---|---|---|
CPH | code and explanation for focus problem | |||
CP2 | iterative vs recursive complete search |
Solution - Chessboard & Queens
next_permutation
Using Since no two queens can be in the same column, let's generate a permutation of length . Then, the represents the column that the -th queen goes on.
By generating all permutations, we can quickly test all possible placements, and count how many are valid.
To make the implementation easier, we can observe that some bottom-left to top-right diagonal can be represented as all squares such that for some . Similarly, some bottom-right to top-left diagonal can be represented as if are zero-indexed.
C++
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;#define pb push_back#define rsz resize#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()using pi = pair<int,int>;#define f first
Java
import java.io.*;import java.util.*;public class Chessboard {public static boolean ok[][] = new boolean[8][8];public static List<Integer> perm = new ArrayList<>();public static boolean[] chosen = new boolean[8];public static int ans = 0;public static void main(String[] args) throws IOException {
Using Backtracking
According to CPH:
A backtracking algorithm begins with an empty solution and extends the solution step by step. The search recursively goes through all different ways how a solution can be constructed.
Since the bounds are small, we can recursively backtrack over all ways to place the queens, storing the current state of the board.
Then, we can try to place a queen at all squares if it isn't attacked by a queen or blocked and recurse, before removing this queen and backtracking.
Finally, when we have placed all the queens and the board's state is valid, then increment the answer.
C++
string g[8];bool sum[15], dif[15], c[8];int ans = 0;void dfs(int r) { // place queen in r-th rowif (r == 8) {++ans; // found valid placementreturn;}for (int i = 0; i < 8; ++i) {
Java
import java.util.*;import java.io.*;public class Main {static String g[];static boolean sum[], dif[], c[];static int ans = 0;static void dfs(int r) { //place queen in row rif (r == 8) {
Python
g = [input() for i in range(8)]d1 = [0] * 15d2 = [0] * 15c = [0] * 8ans = 0def dfs(r): # place queen in r-th rowif r == 8:ans += 1else:for i in range(8):
Pruning
Focus Problem – read through this problem before continuing!
View Internal SolutionBoth of the resources below describe this well so I won't repeat it here.
Resources | ||||
---|---|---|---|---|
CPH | code and explanation for focus problem | |||
CP2 | pruning tips |
Problems
None of these require pruning.
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Bronze | Hard | Show TagsComplete Search, Permutation, Recursion | |||
Bronze | Hard | Show TagsComplete Search, Recursion |
You can find more problems at the CP2 link given above or at USACO Training. However, these sorts of problems appear much less frequently then they once did.
This section is not complete.
make code consistent, improve some of these explanations
Python
What is the time complexity of printing each element of all of the permutations of an array of length ?
Java
What is the time complexity of generating all the permutations of an array of length ?
C++
What is the time complexity of generating all the permutations of an array of length ?