Pythonで指定された条件を満たす順列の個数を求めるプログラム

問題の概要

1からnまでのすべての要素を含む集合Aを考えます。P(A)は、Aに含まれる要素のすべての順列を表します。本記事では、次の2つの条件を満たすP(A)の要素の個数を求めるプログラムを紹介します。

• 条件1: 範囲[1, n]内のすべてのiに対して、A[i] ≠ i である(どの要素も自分自身の位置に配置されない)
• 条件2: k個のインデックスからなる集合 {i1, i2, ..., ik} が存在し、j < k のとき A[ij] = ij+1、かつ A[ik] = i1 となる(長さkの循環構造を持つ)

具体例：n = 3、k = 2 の場合

入力が n = 3、k = 2 のとき、出力は 0 になります。その理由を順を追って確認してみましょう。

配列は1始まりのインデックスで表します。N = 3、K = 2 の場合、まず条件1(A[i] ≠ i)を満たす配列は [3,1,2] と [2,3,1] の2つだけです。次に、K = 2 として考えられるインデックスのペアは次の6通りあります。

[1,2], [1,3], [2,3], [2,1], [3,1], [3,2]

これらのペアが、それぞれの順列において条件を満たすかどうかを検証します。

P(A) → [3,1,2] の場合：

• [1,2]: A[1] ≠ 2
• [1,3]: A[1] = 3 だが A[3] ≠ 1
• [2,3]: A[2] ≠ 3
• [2,1]: A[2] = 1 だが A[1] ≠ 2
• [3,1]: A[3] = 1 だが A[1] ≠ 3
• [3,2]: A[3] ≠ 2

P(A) → [2,3,1] の場合：

• [1,2]: A[1] = 2 だが A[2] ≠ 1
• [1,3]: A[1] ≠ 3
• [2,3]: A[2] = 3 だが A[3] ≠ 2
• [2,1]: A[2] ≠ 1
• [3,1]: A[3] = 1 だが A[1] ≠ 3
• [3,2]: A[3] ≠ 2

このように、どちらの順列にも条件を満たすペアが存在しないため、答えは 0 となります。

解決のための手順

この問題は、以下の手順に従うことで解くことができます。

1. [1, n] の範囲の要素からなる配列のすべての順列 ps を生成します。
2. カウンター c を 0 で初期化します。
3. ps 内の各順列 p について、次の処理を行います。
   • p 内の各インデックス i と値 a を調べ、a == i となる箇所が見つかった場合は、その順列は条件1を満たさないためループを抜けます。
   • 条件1を満たす順列については、各位置 j から順列を辿ってサイクル長を計算します。current := p[j]、cycle_length := 1 とし、current が j に戻るまで current := p[current]、cycle_length := cycle_length + 1 を繰り返します。
   • cycle_length が k と一致したら、c を 1 増やしてループを抜けます。
4. 最終的な c の値を返します。

Pythonでの実装例

理解を深めるために、実際の実装例を見てみましょう。

import itertools

def solve(n, k):
   ps = itertools.permutations(range(n), n)
   c = 0
   for p in ps:
      for i, a in enumerate(p):
         if a == i:
            break
      else:
         for j in range(n):
            current = p[j]
            cycle_length = 1
            while current != j:
               current = p[current]
               cycle_length += 1
            if cycle_length == k:
               c += 1
               break
   return c

n = 3
k = 2
print(solve(n, k))

入力

3, 2

出力

0

コードのポイント

この実装では、itertools.permutations を使ってすべての順列を列挙しています。for-else 構文を活用することで、「固定点(値と位置が一致する要素)を1つも持たない」順列だけを、後続のサイクル判定処理に進めています。その後、各位置から順列をたどってサイクル長を測定し、長さがちょうど k であるサイクルが存在する順列のみをカウントしています。

なお、実装内部では0始まりのインデックスを使用していますが、固定点やサイクル長といった性質は添字の付け方に依存しないため、結果には影響しません。