Python
numpy
数学

完全順列をランダムに生成しよう

全要素が移動する(同じ位置に残らない)shuffle で,全てのパターンが出るとは限らない,という議論がなされていたので私も少し考えてみました.

完全順列になる確率

いわゆる完全順列(撹乱順列, derangement)の問題です.

$$[1, 2,\ldots, n]$$
というリストを
$$[i_1, i_2, \ldots, i_n]$$
と並び替えたとき,$k\neq i_k\ (k=1, \ldots, n)$ となっているものを完全順列といいます.$n$ 個のリストをランダムに並び替えたとき,それが完全順列になっている確率 $p_n$ の極限値は $1/e$($e$ はネイピア数で約 $2.71$ )であることが知られており(収束も非常に速いです),$p_3 = 1/3$ なので,$n\geqq 3$ のとき,だいたい
$$
\frac{1}{3} \leqq p_n\leqq \frac{1}{e} \fallingdotseq 0.367879
$$
という不等式が成り立ちます.つまり,普通にシャッフルすれば,$1/3$ 以上の確率でそれは完全順列になっているということです.そして,もし完全順列じゃなくてもせいぜい $3$ 回シャッフルすればほぼほぼ完全順列を得ることができるということです.よってあまり芸がないのですが,完全順列になるまでシャッフルを繰り返す,が私の結論でした(笑).

import numpy as np

def derange(items):
    if not isinstance(items, np.ndarray):
        items = np.array(items)
    index = np.arange(items.size)
    rand_index = index.copy()
    while 0 in index - rand_index: #0を含んでいれば完全順列でない
        np.random.shuffle(rand_index)
    return items[rand_index]
for i in range(100):
    print(derange(range(4)))
out
[1 0 3 2]
[3 2 0 1]
[1 2 3 0]
[3 2 0 1]
[2 3 1 0]
[3 0 1 2]
[3 2 0 1]
[2 3 1 0]
[1 2 3 0]
[3 2 1 0]
[1 2 3 0]
[2 0 3 1]
[3 2 0 1]
[2 3 1 0]
[3 2 0 1]
[2 3 1 0]
[1 3 0 2]
[1 3 0 2]
[3 2 1 0]
[2 3 0 1]
[2 3 0 1]
[2 0 3 1]
[1 3 0 2]
[1 0 3 2]
[2 3 1 0]
[2 3 0 1]
[1 2 3 0]
[3 2 1 0]
[3 0 1 2]
[2 3 0 1]
[1 2 3 0]
[2 0 3 1]
[3 2 1 0]
[3 2 1 0]
[3 2 1 0]
[1 0 3 2]
[1 2 3 0]
[2 3 1 0]
[3 0 1 2]
[1 2 3 0]
[1 3 0 2]
[2 3 1 0]
[2 3 1 0]
[1 2 3 0]
[2 3 1 0]
[1 2 3 0]
[3 2 1 0]
[3 2 0 1]
[2 0 3 1]
[1 0 3 2]
[2 3 1 0]
[1 2 3 0]
[2 3 0 1]
[1 2 3 0]
[2 3 0 1]
[2 3 1 0]
[3 2 0 1]
[3 2 0 1]
[3 0 1 2]
[3 2 1 0]
[2 3 1 0]
[2 0 3 1]
[1 0 3 2]
[1 2 3 0]
[2 0 3 1]
[1 2 3 0]
[2 3 1 0]
[3 2 1 0]
[1 2 3 0]
[2 0 3 1]
[3 0 1 2]
[1 0 3 2]
[3 0 1 2]
[3 2 1 0]
[1 0 3 2]
[3 2 0 1]
[2 3 0 1]
[2 3 1 0]
[2 3 1 0]
[2 3 1 0]
[1 0 3 2]
[3 2 0 1]
[1 0 3 2]
[1 2 3 0]
[1 0 3 2]
[2 3 1 0]
[1 0 3 2]
[1 2 3 0]
[1 2 3 0]
[2 3 1 0]
[3 0 1 2]
[3 0 1 2]
[3 2 1 0]
[3 0 1 2]
[2 0 3 1]
[1 2 3 0]
[1 3 0 2]
[2 3 1 0]
[2 3 0 1]
[3 0 1 2]

[1, 0, 3, 2] も確認できました.

没ネタ

最初に思いついたのは上のものですが,次のような方法も考えました.しかし,実行速度が遅かったので没にしました.

具体例で説明すると
$$[a, b, c, d, e]$$
をランダムに並び替えて
$$[a, b, e, d, c]$$
となった場合,動いていない $a, b, d$ を巡回させるように
$$\begin{align}
a \longmapsto b\\
b \longmapsto d\\
d \longmapsto a
\end{align}$$
という風に置き換えて,
$$
[b, d, e, a, c]
$$
とするものです.これならば一応確実に完全順列を得られますし,全てのパターンが出てくる可能性はあります(同様な確からしさは不明ですが).しかしこの場合,動かなかったものが $1$ 個しかなかった場合は,巡回させられないので,それ以外のものと置き換える,という場合分けが必要になり,少しコードが複雑になります.