[c++] n個からr個の順列列挙
c++のnext_permutation()は、要素すべてつかって順列列挙することしかできないようなので、
n個からr個の順列列挙するライブラリを作成しました。
列挙した順列を2次元配列(vector)に格納して、返すようにしています。
あまり性能は良くないです。。。
再帰的に走査して順列作成する関数dfs_permutationを作成しましたが、引数が多くなってしまったので、最初の呼び出し用に関数permutationを用意しました。
permutation("順列の元となる配列arr", "取り出す要素数r")
といった感じにして、引数2つで呼べるようにしてます。
内容
関数dfs_permutation
結果を変数resultに格納するようにしています
配列arr： 順列の元になる配列
変数 r： 列挙する数
集合selected： 選択された要素をメモする
配列pattern： 今作成中の順列のパターン1つ
2次元配列 result： 生成した全ての順列パターン
template <class T>
void dfs_permutation(vector<T> &arr, int r, unordered_set<T> &selected, vector<T> &pattern, vector<vector<T>> &result) {
if (r == 0) {
result.push_back(pattern);
return;
}
for (T v : arr) {
if (selected.find(v) == selected.end()) {
selected.insert(v);
pattern.push_back(v);
dfs_permutation(arr, r-1, selected, pattern, result);
pattern.pop_back();
selected.erase(v);
}
}
}
関数permutation
関数dfs_permutationを呼び出すための関数です。
配列arrに、同じ値が含まれている可能性があるため、配列arrのindexを使った配列indexesを用意し、この配列の順列を列挙し、最後に元の配列arrの要素に戻すようにしています。
このあたりの処理も性能が悪くなる原因かもしれません。。。
配列arr： 順列の元になる配列
変数 r： 列挙する数
template <class T>
vector<vector<T>> permutation(vector<T> &arr, int r) {
if (arr.size() < r) {
printf("permutation ERROR: r is larger than arr.size()\n");
exit(1);
}
// 配列arrに、同じ値が含まれている可能性があるため、
// indexを使って順列を列挙し、最後に元の配列の要素に戻す
vector<int> indexes(arr.size());
iota(indexes.begin(), indexes.end(), 0);
unordered_set<int> selected;
vector<int> pattern;
vector<vector<int>> result_indexes;
dfs_permutation<int>(indexes, r, selected, pattern, result_indexes);
vector<vector<T>> result;
for (vector<int> idx_pat : result_indexes) {
vector<T> pat;
for (int i : idx_pat) {
pat.push_back(arr[i]);
}
result.push_back(pat);
}
return result;
}
code
動作例になります。
以下の2つの例になります
・配列[0, 1, 2, 3, 4]から3個取り出す順列
・配列["aa", "aa", "cc", "dd", "ee"]から3個取り出す順列
デバッグ用に、2次元配列の内容を表示する関数を用意していますが、こちらの説明は割愛します。
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
#include <numeric>
// Permutation nPr ----------
template <class T>
void dfs_permutation(vector<T> &arr, int r, unordered_set<T> &selected, vector<T> &pattern, vector<vector<T>> &result) {
if (r == 0) {
result.push_back(pattern);
return;
}
for (T v : arr) {
if (selected.find(v) == selected.end()) {
selected.insert(v);
pattern.push_back(v);
dfs_permutation(arr, r-1, selected, pattern, result);
pattern.pop_back();
selected.erase(v);
}
}
}
template <class T>
vector<vector<T>> permutation(vector<T> &arr, int r) {
if (arr.size() < r) {
printf("permutation ERROR: r is larger than arr.size()\n");
exit(1);
}
// 配列arrに、同じ値が含まれている可能性があるため、
// indexを使って順列を列挙し、最後に元の配列の要素に戻す
vector<int> indexes(arr.size());
iota(indexes.begin(), indexes.end(), 0);
unordered_set<int> selected;
vector<int> pattern;
vector<vector<int>> result_indexes;
dfs_permutation<int>(indexes, r, selected, pattern, result_indexes);
vector<vector<T>> result;
for (vector<int> idx_pat : result_indexes) {
vector<T> pat;
for (int i : idx_pat) {
pat.push_back(arr[i]);
}
result.push_back(pat);
}
return result;
}
// ------------------------------
// Debug用 配列の表示 ----------
template <class T>
void print_vector(vector<T> arr) {
printf("[ ");
for (int i = 0; i < arr.size(); i++) {
//printf("%d", arr[i]);
cout << arr[i];
if (i != (arr.size() - 1)) printf(", ");
}
printf(" ]\n");
}
template <class T>
void print_vector2(vector<T> arr) {
for (int i = 0; i < arr.size(); i++) {
print_vector(arr[i]);
}
}
// ------------------------------
int main() {
vector<int> arr(5);
iota(arr.begin(), arr.end(), 0);
vector<vector<int>> res = permutation(arr, 3);
print_vector2(res);
vector<string> arr2 = {"aa", "aa", "cc", "dd", "ee"};
vector<vector<string>> res2 = permutation(arr2, 3);
print_vector2(res2);
}
結果は、以下のような感じになります
[ 0, 1, 2 ]
[ 0, 1, 3 ]
[ 0, 1, 4 ]
[ 0, 2, 1 ]
[ 0, 2, 3 ]
[ 0, 2, 4 ]
[ 0, 3, 1 ]
[ 0, 3, 2 ]
[ 0, 3, 4 ]
(中略)
[ aa, aa, cc ]
[ aa, aa, dd ]
[ aa, aa, ee ]
[ aa, cc, aa ]
[ aa, cc, dd ]
[ aa, cc, ee ]
[ aa, dd, aa ]
[ aa, dd, cc ]
[ aa, dd, ee ]
(中略)
Discussion