用魔法打败魔法！

Chico 和 Dico 是两位魔术师，他们有一个经典魔术：根据任意四张牌猜第五张牌。但完成这个魔术并不需要任何魔术师的技巧，因为它完全建立在数学原理之上。只需要一点数学知识和充分的练习，你也能表演这个魔术！

GitHub 项目地址：chico-and-dico

Chico 和 Dico 的魔术

Chico 和 Dico 是两位魔术师，他们经常表演的一个魔术是这样的：Chico 将一副 52 张的扑克牌交给一位观众，让他随机抽取其中的 5 张。然后 Chico 将这 5 张牌按一定的顺序重新排列，再将其还给观众。上述整个过程 Dico 都是看不见的。然而，当观众按 Chico 排好的顺序依次展示前四张牌之后，Dico 却能准确地说出第五张牌是什么。

乍一看这个魔术很神奇。随机抽取 5 张牌，你能从前 4 张牌中看出第 5 张牌是什么吗？对于普通人来说，当然不可能。Chico 和 Dico 的秘诀在于 Chico 有机会将扑克重新排序。如果两人事先约定好某种协议，Chico 是有可能通过扑克排列的顺序，向 Dico 传递关于第 5 张牌的信息的。

关键在于如何实现这种协议。

数学模型

在进行分析之前，我们需要把 Chico 和 Dico 的魔术抽象成一个数学模型。

魔术本身已经提供了一些建模信息。我们可以假设一共有 n 张牌，抽取其中的 k 张。在对牌组进行某种排序之后，我们需要利用前 (k - j) 张牌的信息，推测后 j 张牌是什么。

现在我们有 n, j, k 三个变量，下面我们来进一步探究三个变量之间究竟服从何种关系。

首先，我们知道从 n 张牌中抽取 k 张牌一共有 C(n, k) 种组合方式，而 (k - j) 张牌的排列方式则有 A(n, k-j) 种。按照模型的要求，我们要用后者对前者的信息进行编码。根据信息论中的信源编码理论，至少有：C(n, k) <= A(n, k-j)。

根据上述不等式，我们有： $$ C(n, k) = \frac{n!}{(n-k)!k!} \leq \frac{n!}{(n-k+j)!} = A(n, k-j), \\ 即 (n - k + j)! \leq k!(n - k)! $$ 故 n, j, k 三个变量至少需要满足： $$ (n - k + j)! \leq k!(n - k)! $$

算法实现

现在一切都还很抽象。

为了更好地理解 Chico 对牌组的编码，以及 Dico 对牌组的解码。我们用一个实例复现一下魔术现场的情景。

根据我们的模型和文章开头对魔术的描述。显然，我们有 n = 52, k = 5, j = 1。

此外我们还作如下约定：

1. cards 代表所有 52 张扑克牌组成的列表；
2. selected_cards 代表观众选出的 5 张牌组成的列表；
3. 被 Chico 排好序的牌组放入列表 reordered_cards 中；
4. 约定 s = sum(selected_cards) mod k!；
5. 一般情况下，q 代表商（初始化那次除外），r 代表余数。

好了。现在我宣布，从这里开始，这个广场就叫作魔术广场！

魔术正式开始

第一步，我们让观众取出 5 张牌。假设观众取出的是 {18, 50, 12, 19, 4}。我们先要对这 5 张牌从小到大进行排序。

selected_cards = [18, 50, 12, 19, 4]
selected_cards = sorted(selected_cards)
# selected_cards = [4, 12, 18, 19, 50]

第二步，计算 s = sum(selected_cards) mod k! 的值。

s = sum(selected_cards) % factorial(5)
# s = 103

第三步，对这 5 张牌按如下规则进行编码：

q = s
for i in range(5, 0, -1):
    q, r = divmod(q, i)
    reordered_cards.append(selected_cards.pop(r))

为了理解这一步做了什么，我们将上述循环展开。

最终，我们得到一个列表 reordered_cards = [12, 18, 50, 4, 19]。

第四步，我们对上一步中得到的列表 [12, 18, 50, 4, 19] 进行分割，将前 4 张牌 [12, 18, 50, 4] 送入解码器中，最后一个值 19 作为答案保存下来，用于最后魔术成功与否的判定。

第五步，将前 4 张牌 [12, 18, 50, 4] 解码。此步相当于是第三步的逆过程。我们将牌组按如下规则进行解码：

for i in range(1, 5, 1):
    q_list[i] = i * q_list[i-1] + r_list[i-1]
    if i != 4:
        visible_cards.append(first_four[i])
        r_list[i] = sorted(visible_cards).index(first_four[i])

为了理解这一步做了什么，我们将上述循环展开。

第六步，推测第五张牌的值的取值范围。

经过迭代后，我们知道 $ q_5 = 20 $，虽然不知道 $ r_5 $ 等于多少，但是我们知道 $ r_5 $ 的范围为 $ 0 \leq r_5 \leq 4 $。又因为 $s = 5 * q_5 + r_5 $, 故有 $ 100 \leq s \leq 104 $。

此外，我们还知道 s = (v + sum([12, 18, 50, 4]))。设第五张牌的值为 v，有： $$ 100 \leq (v + sum([12, 18, 50, 4])) \bmod 5! \leq 104 \\ 100 \leq (v + 84) \bmod 5! \leq 104 \\ 16 \leq v \bmod 120 \leq 20 $$ 又 $ 1 \leq v \leq 52 $，故： $$ 16 \leq v \leq 20 $$ 上述过程的代码如下：

# 总结当前信息
sum_of_first_four = sum(first_four)
q = q_list[-1]

# 计算编码时q的初始值s的范围
range_l = 5 * q_list[-1]  # range_l <= s的值
range_r = 5 * q_list[-1] + 4  # s的值 <= range_r

# 计算第五张牌的值v的范围
times = 0
while True:
    v_l = range_l + times * factorial(5) - sum_of_first_four
    v_r = range_r + times * factorial(5) - sum_of_first_four
    times += 1
    if (v_r >= 1) and (v_l <= 52):
        break
    elif times > 2:
        raise ValueError('can not find the range of v.')

第七步，尝试可行域中的每一种取值。唯一可行的取值即为第五张牌的值。

# 猜解码时第五次迭代的余数r
for v in range(v_l, v_r+1):
    if v not in first_four:
        temp = first_four[:]
        temp.append(v)
        test_r = sorted(temp).index(v)
        s = 5 * q + test_r
        guess_v = s + (times - 1) * factorial(5) - sum_of_first_four
        if v == guess_v:
            return v

参考：

1. Chico and Dico
2. Chico and Dico —— 根据任意4张扑克猜第5张牌