Python 裡, 有一個串列裡的東西, 我們想做排列組合, 可以用 itertools
。這算一個標準套件!
from itertools import permutations
我們先來, 比如說 1, 2, 3, 4, 5 這樣的串列。
L = [1, 2, 3, 4, 5]
找出所有 ($5!$ 種) 排列的方式。
permutations(L)
<itertools.permutations at 0x103720ca8>
要看到裡面的內容, 可以用 list
指令, 變成一個, 嗯, list。
S5 = list(permutations(L))
可以看看是不是總共有 $5! = 120$ 個。
len(S5)
120
也可以看其中一個...
S5[87]
(4, 3, 2, 5, 1)
進行方式很類似... 比如我們五個元素, 要取出兩個...
from itertools import combinations
C2 = list(combinations(L, 2))
C2
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
len(C2)
10
果然有 $C(5,2) = 10$ 個。
Derangement 是有名的、像是「有 $n$ 個人把帽子丟到空中, 最後大家拿回帽子都不是自己的情況, 一共有幾個可能?」
如果 $n$ 個元素的 derangement 一共有 $D_n$ 個可能, 我們在很多地方都可以看到這可愛公式:
$$D_n = n D_{n-1} + (-1)^n \mbox{。}$$我們又很容易知道 $D_1 = 0, D_2 = 1$, 於是可以算出:
$D_3 = 3 \times D_2 - 1= 2,$
還有 $D_4 = 9, D_5 = 44$ 等等。
不過, 要實際算出 derangement 的可能性比較複雜, 我們可以參考這裡的討論, 列出所有可能的 derangement。
def derangement(x):
p = permutations(x)
return (i for i in p if not any(i[k] == x[k] for k in range(len(x))))
比如說, 我們可以算所有五個元素串列的 derangement。
D = list(derangement(L))
看看是不是 44 個?
len(D)
44
當然, 你也可欣賞一下 $44$ 個全部列出來的樣子...
D
[(2, 1, 4, 5, 3), (2, 1, 5, 3, 4), (2, 3, 1, 5, 4), (2, 3, 4, 5, 1), (2, 3, 5, 1, 4), (2, 4, 1, 5, 3), (2, 4, 5, 1, 3), (2, 4, 5, 3, 1), (2, 5, 1, 3, 4), (2, 5, 4, 1, 3), (2, 5, 4, 3, 1), (3, 1, 2, 5, 4), (3, 1, 4, 5, 2), (3, 1, 5, 2, 4), (3, 4, 1, 5, 2), (3, 4, 2, 5, 1), (3, 4, 5, 1, 2), (3, 4, 5, 2, 1), (3, 5, 1, 2, 4), (3, 5, 2, 1, 4), (3, 5, 4, 1, 2), (3, 5, 4, 2, 1), (4, 1, 2, 5, 3), (4, 1, 5, 2, 3), (4, 1, 5, 3, 2), (4, 3, 1, 5, 2), (4, 3, 2, 5, 1), (4, 3, 5, 1, 2), (4, 3, 5, 2, 1), (4, 5, 1, 2, 3), (4, 5, 1, 3, 2), (4, 5, 2, 1, 3), (4, 5, 2, 3, 1), (5, 1, 2, 3, 4), (5, 1, 4, 2, 3), (5, 1, 4, 3, 2), (5, 3, 1, 2, 4), (5, 3, 2, 1, 4), (5, 3, 4, 1, 2), (5, 3, 4, 2, 1), (5, 4, 1, 2, 3), (5, 4, 1, 3, 2), (5, 4, 2, 1, 3), (5, 4, 2, 3, 1)]