C++で最初に減少し、その後増加する順列の個数を求める方法

変数 num が与えられ、[1, num] の範囲内の数字を使った順列のうち、「最初に減少し、その後増加する」というパターンを持つ順列の個数を求めるのが目的です。例えば num=3 の場合、扱う数字は 1、2、3 であり、条件を満たす順列は [3, 1, 2] と [2, 1, 3] の 2 つです。

すべての順列において、数字が「減少」から「増加」へと切り替わる位置は、最小値である 1 の配置場所によって決まります。1 の後ろでは数字が増加し始めるため、減少後に増加する順列を実現するには、1 が 2 番目から num−1 番目の間の位置に置かれる必要があります。

もし 1 が先頭にあれば系列は完全な増加順序となり、逆に末尾にあれば完全な減少順序になってしまいます。

考え方

num=4 の場合を例に具体的に見てみましょう。

• 1 を 2 番目に配置する場合:[-, 1, -, -] という形になり、1 番目の位置には (2, 3, 4) の中から 1 つを選びます。例えば 2 を選ぶと [2, 1, 3, 4] となります。このケースでは ³C₁ 通りの順列が可能です。

• 1 を 3 番目に配置する場合:[-, -, 1, -] という形になり、1 番目と 2 番目の位置には (2, 3, 4) の中から 2 つを選びます。合計 ³C₂ 通りの順列になります。

したがって、num=4 の場合の順列の総数は ³C₁ + ³C₂ となります。

これを一般化すると、任意の num = x に対して、条件を満たす順列の個数は次の式で表せます。

^x-1C₁ + ^x-1C₂ + … + ^x-1C_x-2 = 2^x-1 − 2(二項定理より)

具体例

例 1

入力:num = 4

出力:最初に減少し、その後増加する順列の個数:6

説明:条件を満たす順列は以下の通りです。

[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 が 2 番目の位置
[ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 が 3 番目の位置

例 2

入力:num = 6

出力:最初に減少し、その後増加する順列の個数:30

説明:一部の順列は以下の通りです。

[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ],
[ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ] …… [ 6, 5, 4, 3, 1, 2 ]

プログラムで使用するアプローチ

このアプローチでは、二項定理を利用して上記の公式から直接順列の個数を計算します。あわせて、i^num を返す関数 value(long long i, long long num) を作成します。この関数は繰り返し二乗法(バイナリ法)により、O(log n) の計算量でべき乗を高速に求められる点がポイントです。

• 変数 num を入力として受け取ります。

• 関数 permutations_increase_decrease(int num) は num を受け取り、1 から num までの数字で構成される「最初に減少し、その後増加する」順列の個数を返します。

• 関数 value(long long i, long long num) は (i^num) % temp を計算します。ここで temp = 1000000007 です。

• permutations_increase_decrease(int num) の内部で temp = 1000000007 を設定します。

• num が 1 の場合、条件を満たす順列は存在しないため 0 を返します。

• それ以外の場合は、公式に従って count = (value(2, num − 1) − 2) % temp とします。

• count を結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
long long value(long long i, long long num){
    int temp = 1000000007;
    if (num == 0){
        return 1;
    }
    long long j = value(i, num / 2) % temp;
    j = (j * j) % temp;
    if(num & 1){
        j = (j * i) % temp;
    }
    return j;
}
int permutations_increase_decrease(int num){
    int temp = 1000000007;
    if (num == 1){
        return 0;
    }
    int count = (value(2, num - 1) - 2) % temp;
    return count;
}
int main(){
    int num = 4;
    cout<<"Count of permutations that are first decreasing then increasing are: "<<permutations_increase_decrease(num);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Count of permutations that are first decreasing then increasing are: 6