🙆‍♀️

[c++] n個からr個の順列列挙

2022/10/05に公開約4,500字

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

ログインするとコメントできます