アルゴリズム

[Python] 完全順列をランダムな順列に並び替える方法

2025-01-18更新日: 2025-01-18

完全順列(derangement)は、元のリストの要素が一つも元の位置にない順列です。

Pythonで完全順列をランダムに生成するには、random.shuffle()を使ってランダムな順列を作成し、各要素が元の位置にないかを確認する必要があります。

itertools.permutations()で全ての順列を生成し、その中から完全順列を選ぶ方法もありますが、効率的ではありません。

目次から探す

完全順列(derangement)とは
Pythonで完全順列を生成する方法
完全順列をランダムに生成するアルゴリズム
完全順列の検証方法
応用例：完全順列を使った問題解決
まとめ

完全順列(derangement)とは

完全順列(derangement)とは、与えられた要素の順列の中で、元の位置に戻らないように並べ替えたものを指します。

例えば、3つの要素 {1, 2, 3} の完全順列は {2, 3, 1} や {3, 1, 2} ですが、{1, 2, 3} は元の位置に戻っているため完全順列ではありません。

完全順列は、組合せ論や確率論において重要な概念であり、特に秘密交換問題や暗号理論などの応用に利用されます。

完全順列の数は、 $! n$ (nの階乗の完全順列)で表され、次のように計算されます：

$! n = (n - 1) (! (n - 1) +! (n - 2))$

このように、完全順列は特定の条件を満たす順列の集合として、さまざまな数学的問題において重要な役割を果たします。

Pythonで完全順列を生成する方法

itertools.permutationsを使った順列生成

Pythonの標準ライブラリであるitertoolsを使用すると、簡単に順列を生成できます。

itertools.permutations関数を使うことで、与えられたリストのすべての順列を取得できます。

import itertools
# 元のリスト
elements = [1, 2, 3]
# 順列を生成
permutations = list(itertools.permutations(elements))
# 結果を表示
print(permutations)

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

このコードでは、リスト[1, 2, 3]のすべての順列を生成し、タプルのリストとして出力しています。

完全順列の条件を確認する方法

完全順列を確認するためには、生成した順列が元のリストの要素をすべて含み、かつ各要素が元の位置に戻らないことを確認する必要があります。

以下の関数を使って、完全順列かどうかをチェックできます。

def is_derangement(original, perm):
    return all(original[i] != perm[i] for i in range(len(original)))
# 例
original = [1, 2, 3]
perm = [2, 3, 1]
# 完全順列かどうかを確認
print(is_derangement(original, perm))

True

この関数は、元のリストと生成した順列を比較し、すべての要素が元の位置にない場合にTrueを返します。

完全順列を効率的に生成するアルゴリズム

完全順列を効率的に生成するためには、再帰的なアプローチや動的計画法を用いることが一般的です。

以下は、再帰を用いた完全順列の生成例です。

def derangement(n):
    if n == 0:
        return 1
    elif n == 1:
        return 0
    else:
        return (n - 1) * (derangement(n - 1) + derangement(n - 2))
# 完全順列の数を表示
n = 4
print(derangement(n))

このコードは、与えられた数nに対する完全順列の数を計算します。

random.shuffleを使ったランダムな順列生成

random.shuffleを使用すると、リストの要素をランダムに並べ替えることができます。

これを利用して、完全順列を生成することも可能です。

ただし、生成された順列が完全順列であるかどうかを確認する必要があります。

import random
def random_derangement(elements):
    while True:
        shuffled = elements[:]
        random.shuffle(shuffled)
        if is_derangement(elements, shuffled):
            return shuffled
# 元のリスト
elements = [1, 2, 3]
# ランダムな完全順列を生成
result = random_derangement(elements)
print(result)

[3, 1, 2]

このコードでは、元のリストをランダムにシャッフルし、完全順列であるかを確認して、条件を満たすまで繰り返します。

完全順列をランダムに生成するアルゴリズム

Fisher-Yatesアルゴリズムの概要

Fisher-Yatesアルゴリズムは、リストの要素をランダムに並べ替えるための効率的な手法です。

このアルゴリズムは、リストの各要素を一度だけ訪れ、ランダムに選ばれた要素と交換することで、すべての順列が等確率で生成されます。

具体的には、リストの最後の要素から始めて、各要素をランダムに選ばれた前の要素と交換します。

この方法により、O(n)の時間計算量でランダムな順列を生成できます。

Fisher-Yatesアルゴリズムを使ったランダムな順列生成

Fisher-Yatesアルゴリズムを用いて、リストの要素をランダムに並べ替える方法は以下の通りです。

import random
def fisher_yates_shuffle(elements):
    n = len(elements)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)  # 0からiまでのランダムなインデックス
        elements[i], elements[j] = elements[j], elements[i]  # 要素を交換
    return elements
# 元のリスト
elements = [1, 2, 3, 4]
# ランダムな順列を生成
shuffled = fisher_yates_shuffle(elements[:])  # 元のリストを変更しないためにコピー
print(shuffled)

[3, 1, 4, 2]

このコードでは、Fisher-Yatesアルゴリズムを使用して、リストの要素をランダムに並べ替えています。

完全順列をランダムに生成するための工夫

完全順列を生成する際には、単に要素をランダムに並べ替えるだけでは不十分です。

元の位置に戻らないようにするためには、生成した順列が完全順列であるかを確認する必要があります。

以下の工夫を行うことで、完全順列を効率的に生成できます。

再試行: Fisher-Yatesアルゴリズムで生成した順列が完全順列でない場合、再度シャッフルを行う。
条件付き生成: 元のリストの要素を元の位置に戻さないように、特定の条件を満たすように要素を選択する。

Pythonでの実装例

以下は、Fisher-Yatesアルゴリズムを用いて完全順列を生成するPythonの実装例です。

import random
def is_derangement(original, perm):
    return all(original[i] != perm[i] for i in range(len(original)))
def random_derangement(elements):
    while True:
        shuffled = fisher_yates_shuffle(elements[:])  # シャッフル
        if is_derangement(elements, shuffled):  # 完全順列か確認
            return shuffled
# 元のリスト
elements = [1, 2, 3]
# ランダムな完全順列を生成
result = random_derangement(elements)
print(result)

[2, 3, 1]

このコードでは、Fisher-Yatesアルゴリズムを使用してリストをシャッフルし、完全順列であるかを確認することで、条件を満たすまで繰り返します。

これにより、完全順列を効率的に生成することができます。

完全順列の検証方法

元のリストと比較して検証する方法

完全順列を検証するための基本的な方法は、生成した順列が元のリストの要素をすべて含み、かつ各要素が元の位置に戻らないことを確認することです。

以下の関数を使って、元のリストと生成した順列を比較し、完全順列であるかを検証できます。

def is_derangement(original, perm):
    # 元のリストと比較して完全順列か確認
    return sorted(original) == sorted(perm) and all(original[i] != perm[i] for i in range(len(original)))
# 例
original = [1, 2, 3]
perm = [2, 3, 1]
# 完全順列かどうかを確認
print(is_derangement(original, perm))

True

この関数では、まず元のリストと生成した順列が同じ要素を持つかを確認し、その後、各要素が元の位置に戻っていないかをチェックします。

all()関数を使った簡単な検証

Pythonの組み込み関数all()を使用すると、条件を満たすかどうかを簡潔に確認できます。

以下のように、all()を使って完全順列を検証することができます。

def is_derangement_with_all(original, perm):
    # 元のリストと比較して完全順列か確認
    return sorted(original) == sorted(perm) and all(original[i] != perm[i] for i in range(len(original)))
# 例
original = [1, 2, 3]
perm = [3, 1, 2]
# 完全順列かどうかを確認
print(is_derangement_with_all(original, perm))

True

このコードでは、all()関数を使って、すべての要素が元の位置に戻っていないかを確認しています。

これにより、コードが簡潔になり、可読性が向上します。

完全順列の検証を自動化する方法

完全順列の検証を自動化するためには、生成した順列のリストをループで回し、すべての順列が完全順列であるかを確認する関数を作成できます。

以下は、その実装例です。

import itertools
def validate_all_derangements(original):
    # 元のリストのすべての順列を生成
    permutations = itertools.permutations(original)
    # 完全順列のリストを作成
    derangements = [perm for perm in permutations if is_derangement(original, perm)]
    return derangements
# 元のリスト
original = [1, 2, 3]
# 完全順列を自動的に検証
result = validate_all_derangements(original)
print(result)