C++で配列の完全順列（撹乱順列）の数を求めるアルゴリズム

1からnまでの数字が昇順に並んだ長さnの配列があるとします。この配列から生成できる「完全順列（derangement：撹乱順列）」の総数を求めるのが本記事のテーマです。

組合せ数学において、完全順列とは、集合の要素を並べ替えた順列のうち、どの要素も元の位置に現れないようなものを指します。答えは非常に大きな数になる可能性があるため、10⁹ + 7で割った余りを返すこととします。

例えば、入力が3の場合、出力は2になります。元の配列が [1, 2, 3] であるとき、条件を満たす完全順列は [2, 3, 1] と [3, 1, 2] の2通りだけだからです。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解けます。手順は以下の通りです。

• m := 10⁹ + 7 と定義する
• 関数 add(a, b)：((a mod m) + (b mod m)) mod m を返す
• 関数 mul(a, b)：((a mod m) × (b mod m)) mod m を返す
• メイン処理では以下を実行する
• n が 1 の場合は 0 を返す（1つの要素を元の位置以外に置くことは不可能なため）
• n が 2 の場合は 1 を返す（[2, 1] のみが有効）
• サイズ (n + 1) の配列 dp を用意する
• dp[2] := 1 と初期化する
• i を 3 から n まで増やしながら、dp[i] := mul(i − 1, add(dp[i − 2], dp[i − 1])) を計算する
• 最後に dp[n] を返す

漸化式のポイント

このアルゴリズムの中核となる漸化式は次の通りです。

dp[i] = (i − 1) × (dp[i − 1] + dp[i − 2])

この式が成り立つ理由は次の通りです。i番目の要素は、(i − 1) 個ある他の位置のいずれかに必ず移動します。移動先の要素 j がどこに移動するかで場合分けすると、j が i番目の位置に来るケース（残り i − 2 個の完全順列：dp[i − 2] 通り）と、そうでないケース（残り i − 1 個の完全順列：dp[i − 1] 通り）に分けられます。これらを合計して (i − 1) 倍することで、上記の漸化式が導かれます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
    return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
    return ((a % m) * (b % m)) % m;
}
class Solution {
public:
    int findDerangement(int n) {
        int ret = 0;
        if (n == 1)
            return 0;
        if (n == 2)
            return 1;
        vector<lli> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = mul(i - 1, add(dp[i - 2], dp[i - 1]));
        }
        return dp[n];
    }
};
main(){
    Solution ob;
    cout << (ob.findDerangement(3));
}

入力

3

出力

2

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。dp 配列は直前の2つの値しか参照しないため、変数2つだけで管理すれば空間計算量を O(1) に削減することも可能です。