C++でちょうどK個の転倒（インバージョン）を持つ順列の数を求める方法

問題概要

配列において、a[i] > a[j] かつ i < j を満たすペア (a[i], a[j]) のことを「転倒（インバージョン）」と呼びます。この問題では、2つの整数 N と K が与えられ、1から N までの数を使った順列のうち、転倒数がちょうど K に一致するものが何通り存在するかを求めます。

例

入力：N = 4, K = 1
出力：3
説明：1〜4の順列には 1234, 1243, 1324, 2134 などがあります。このうち転倒が1つだけのものは 1243, 1324, 2134 の3通りです。

入力：N = 3, K = 2
出力：3
説明：1〜3の順列は 123, 132, 213, 231, 312, 321 の6通りです。このうち転倒が2つのものは 231, 312, 321 の3通りです。

解法のアプローチ

1. 全探索（ブルートフォース）

最も単純な方法は、まず1から N までの数のすべての順列を生成し、それぞれについて転倒数を数えて K と一致するかを確認するものです。一致した場合にカウンタを増やしていきます。ただし、順列の総数は N! で急激に増えるため、N が大きくなると現実的な時間では計算できません。

2. 効率的なアプローチ（メモ化再帰）

効率的な解法では、再帰的な構造に着目します。N 個の数の順列を考えるとき、最大の数 N を (N−1) 個の数の順列に挿入することを考えます。N を末尾から d 番目の位置に挿入すると、新たに d 個の転倒が発生します。したがって、「転倒数が K−d である (N−1) 個の数の順列」の数を足し合わせることで、答えが求まります。これを漸化式で表すと次のようになります。

find_permutations(N, K) = Σ (i = 0 から K まで) find_permutations(N−1, K−i)

この再帰をそのまま実装すると重複計算が多発するため、結果を二次元配列にキャッシュするメモ化を行うことで、時間計算量 O(N × K) で効率的に求められます。

C++による実装

#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int arr[X][X]; // メモ化用のキャッシュ

// 再帰関数
int find_permutations(int N_numbers, int K_inversion){
    if (N_numbers == 0){
        return 0;              // N が 0 になったら 0 を返す
    }
    if (K_inversion == 0)
        return 1;              // K が 0 になったら 1 を返す
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion]; // 計算済みならキャッシュを返す
    int result = 0;
    for (int i = 0; i <= K_inversion; i++){
        if (i <= N_numbers - 1)
            result += find_permutations(N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}

// メイン関数
int main(){
    int N, K;
    cin >> N;                  // ユーザーから入力を受け取る
    cin >> K;
    cout << find_permutations(N, K);
    return 0;
}

実行例

入力：N = 4, K = 3
出力：6

N = 4、K = 3 の場合、転倒をちょうど3つ持つ順列は6通り存在することが確認できます。

まとめ

この記事では、1から N までの数の順列のうち、転倒をちょうど K 個持つものの個数を求める問題を取り上げました。全探索では N! に比例した時間がかかりますが、最大値を挿入する位置に着目した再帰とメモ化を組み合わせることで、O(N × K) の時間計算量で効率的に解くことができます。紹介したプログラムはC++だけでなく、C、Java、Python など他の言語でも同様に実装可能です。皆さんのアルゴリズム学習の一助となれば幸いです。