Generating Permutations, Combinations and Variations

Lesson 6 of 7 · Recursion and backtracking

Many 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.

Before you start: prerequisites – Backtracking.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Terms and the number of possibilities

What we chooseNameNumberExample for {1, 2, 3}
an arrangement of all n elementspermutationsn!123, 132, 213, 231, 312, 321
k of n, the order does not mattercombinationsC(n, k)k = 2: 12, 13, 23
k of n, the order mattersvariationsn!/(n−k)!k = 2: 12, 13, 21, 23, 31, 32
k times one of n (with repetition)variations with repetitionnkk = 2: 11, 12, 13, 21, …, 33
any choicesubsets2n{}, {1}, {2}, {3}, {1,2}, …

How these numbers are computed without generating is explained in the lesson Combinatorics (SR).

Permutations – recursively

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.

Combinations k of n

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;
}

Subsets with bits

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;
}

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

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 13

Output

11
13
31
33
TASK 02Difficulty: medium

The largest number divisible by 3

From 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.

Example 1

Input

1052

Output

-1

Example 2

Input

123

Output

321
TASK 03Difficulty: medium

Choosing a team

From 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?

Example

Input

4 2 9
5 3 6 4

Output

4
Common mistakes and tips
  • For next_permutation the array must be sorted at the start – otherwise permutations are skipped.
  • Generate combinations in increasing order (from = x + 1), otherwise you get variations with duplicates.
  • Before writing the code compute the number of possibilities: 10! is 3.6 million (fine), 12! is 479 million (too slow to print).
  • 1 << n is 2n; for n ≥ 31 use 1LL << n.

Check your knowledge

Open the quiz

Mini quiz: permutations and combinations

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)?