C++でnext_permutationを使わずに順列を列挙する

2020-06-03 c++

配列が渡されてそれを並び替えてできる全ての順列を返す問題。まさにSTLのalgorithmに辞書順で次の順列を返すnext_permutation()というのがあって次のようにするだけでできてしまう。

vector<vector<int>> ret;
sort(nums.begin(), nums.end());
do {
    ret.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return ret;

せっかくなのでこれを使わず実装してみた。あるindexの要素とそれ以降の全ての要素をそれぞれswapすることでそのindexに入り得る全ての値を網羅し、それら全ての配列に対して対象のindexを一つ増やして同じ処理を再帰的に繰り返す。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        return _permute(nums, 0);
    }
    
    vector<vector<int>> _permute(vector<int> nums, int swap_index) {
        vector<vector<int>> ret;
        if (swap_index >= nums.size()) {
            return {nums};
        }
        for(int i = swap_index; i < nums.size(); i++) {
            swap(nums[swap_index], nums[i]);
            auto v = _permute(nums, swap_index+1);
            copy(v.begin(), v.end(), back_inserter(ret));
            swap(nums[swap_index], nums[i]);
        }
        return ret;
    }
};