PIN codes
A PIN has k digits (k ≤ 6), and only the digits from a given word c (e.g. 137) are allowed. Print all the possible PINs in increasing order.
Example
Input
2 13Output
11
13
31
33Many competition tasks ask you to try all the arrangements or all the choices of elements. Here are ready-made templates for generating permutations, combinations, variations and subsets – recursively and with the function next_permutation.
| What we choose | Name | Number | Example for {1, 2, 3} |
|---|---|---|---|
| an arrangement of all n elements | permutations | n! | 123, 132, 213, 231, 312, 321 |
| k of n, the order does not matter | combinations | C(n, k) | k = 2: 12, 13, 23 |
| k of n, the order matters | variations | n!/(n−k)! | k = 2: 12, 13, 21, 23, 31, 32 |
| k times one of n (with repetition) | variations with repetition | nk | k = 2: 11, 12, 13, 21, …, 33 |
| any choice | subsets | 2n | {}, {1}, {2}, {3}, {1,2}, … |
How these numbers are computed without generating is explained in the lesson Combinatorics (SR).
At every position, in order, we put one of the numbers not used yet. The array used remembers which numbers are already in the permutation.
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> perm;
vector<bool> used;
void generate() {
if ((int)perm.size() == n) { // the permutation is complete
for (int x : perm) cout << x << " ";
cout << "\n";
return;
}
for (int x = 1; x <= n; x++) {
if (used[x]) continue;
used[x] = true; perm.push_back(x); // choose
generate(); // explore
used[x] = false; perm.pop_back(); // undo
}
}
int main() {
cin >> n;
used.assign(n + 1, false);
generate();
return 0;
}
The permutations come out in lexicographic order, because at every position the numbers are tried from the smallest.
In C++ the function next_permutation (header <algorithm>) turns an array into the next permutation in lexicographic order and returns false when it has reached the last one. The array must be sorted at the start. If the array contains equal elements, every different permutation is obtained exactly once.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
cin >> s;
sort(s.begin(), s.end()); // we start from the smallest permutation
int count = 0;
do {
cout << s << "\n";
count++;
} while (next_permutation(s.begin(), s.end()));
cout << "Total: " << count << endl;
return 0;
}
For the input aab the program prints aab, aba, baa and Total: 3.
With combinations the order does not matter, so to avoid getting the same choice twice, we choose the numbers in increasing order: after the number x we choose the next one from x + 1.
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> chosen;
void combinations(int from) {
if ((int)chosen.size() == k) {
for (int x : chosen) cout << x << " ";
cout << "\n";
return;
}
// pruning: enough numbers are left to fill the choice
for (int x = from; x <= n - (k - (int)chosen.size()) + 1; x++) {
chosen.push_back(x);
combinations(x + 1);
chosen.pop_back();
}
}
int main() {
cin >> n >> k;
combinations(1);
return 0;
}
A subset of a set of n elements can be represented by a number from 0 to 2n − 1: if the i-th bit is one, the element i is in the subset. This is shorter than recursion and fast enough for n ≤ 20.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int mask = 0; mask < (1 << n); mask++) {
cout << "{ ";
for (int i = 0; i < n; i++)
if (mask & (1 << i)) // is the i-th bit one
cout << i + 1 << " ";
cout << "}\n";
}
return 0;
}
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
A PIN has k digits (k ≤ 6), and only the digits from a given word c (e.g. 137) are allowed. Print all the possible PINs in increasing order.
2 1311
13
31
33From the digits of a given number (at most 9 digits) make a number that uses all the digits, is divisible by 3 and is the largest possible. If there is no such number, print -1.
1052-1123321From n students (n ≤ 15) with given points a team of exactly k students is chosen. How many teams have a sum of points of at least P?
4 2 9
5 3 6 44next_permutation the array must be sorted at the start – otherwise permutations are skipped.from = x + 1), otherwise you get variations with duplicates.1 << n is 2n; for n ≥ 31 use 1LL << n.1. How many permutations does a set of 5 elements have?
2. What does next_permutation return when the array is the last permutation?
3. Which number represents the subset {1, 3} of the set {1, 2, 3} in bit notation (bit 0 = element 1)?