itertools

ソースコード

 1#include<bits/stdc++.h>
 2using namespace std;
 3
 4// 2N個のものをN個のペアに分ける方法
 5// (2*n-1) * (2*n-3) * (2*n-5) * ... * 1
 6vector<vector<pair<int, int>>> get_2n_to_n_pair(int n) {
 7    vector<vector<pair<int, int>>> result;
 8    vector<pair<int, int>> tmp;
 9    vector<bool> is_used(n, false);
10    auto dfs = [&] (auto &&dfs) -> void {
11        if ((int)tmp.size() == n) {
12            result.push_back(tmp);
13            return;
14        }
15        int left = -1;
16        for (int i = 0; i < 2*n; ++i) {
17            if (!is_used[i]) {
18                left = i;
19                break;
20            }
21        }
22        assert(left != -1);
23        is_used[left] = true;
24        for (int right = 0; right < 2*n; ++right) {
25            if (!is_used[right]) {
26                tmp.emplace_back(left, right);
27                is_used[right] = true;
28                dfs(dfs);
29                tmp.pop_back();
30                is_used[right] = false;
31            }
32        }
33        is_used[left] = false;
34    };
35
36    dfs(dfs);
37    return result;
38}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/others/itertools.cpp