详解欧拉计划第622题：完美洗牌

创作时间:

作者:

@小白创作中心

详解欧拉计划第622题：完美洗牌

引用

CSDN

https://blog.csdn.net/slofslb/article/details/126197980

欧拉计划第622题探讨了一种特殊的洗牌方式——完美洗牌。这种洗牌方式将牌堆平分为两半，然后将下半部分的牌依次插入到上半部分牌之间。本文将详细介绍如何通过编程和数学推理解决这个问题，计算使牌堆恢复原状所需的最少洗牌次数，并找出所有满足特定洗牌次数恢复原状的牌数总和。

问题描述

完美洗牌的具体操作如下：将牌堆平分为两份，左手持上半部分，右手持下半部分，然后将右手的牌严格交叉到左手的牌中，即右手的第一张牌置于左手第一张牌之后，右手第二张牌置于左手第二张牌之后，依此类推。值得注意的是，这种洗牌方式不会改变牌堆顶部和底部的两张牌的位置。

记 (s(n)) 为使牌堆恢复原状所需的最少连续洗牌次数，其中 (n) 为偶数。例如，52张标准扑克牌只需8次洗牌即可恢复原状，即 (s(52) = 8)。同样，86张牌也只需8次洗牌恢复原状，所有满足 (s(n) = 8) 的 (n) 的和为412。

解题过程

第一步：实现完美洗牌算法

首先，我们需要实现一个函数来模拟完美洗牌的过程。假设有一副12张牌，编号从0到11，初始时按顺序排列。一次完美洗牌后的结果如下：

def perfect_shuffle(cards):
    half = len(cards) // 2
    shuffled = []
    for i in range(0, half):
        shuffled.append(cards[i])
        shuffled.append(cards[half + i])
    return shuffled

cards = list(range(12))
print(cards)
for i in range(5):
    cards = perfect_shuffle(cards)
    print(cards)

用12张牌洗5次的结果如下：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 6, 1, 7, 2, 8, 3, 9, 4, 10, 5, 11]
[0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8, 11]
[0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4, 11]
[0, 9, 7, 5, 3, 1, 10, 8, 6, 4, 2, 11]
[0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11]

第二步：计算恢复原状所需的洗牌次数

接下来，我们需要计算对于 (n) 张牌，需要多少次完美洗牌才能恢复原状。这可以通过不断洗牌并计数来实现。

def shuffle_times(n):
    cards = list(range(n))
    shuffled = perfect_shuffle(cards)
    count = 1
    while shuffled != cards:
        shuffled = perfect_shuffle(shuffled)
        count += 1
    return count

assert shuffle_times(52) == 8
assert shuffle_times(86) == 8

第三步：找出所有满足 (s(n) = 8) 的 (n) 并求和

为了找出所有满足 (s(n) = 8) 的 (n)，我们遍历一定范围内的偶数，并计算它们的洗牌次数。

def sum_s(n):
    total = 0
    for i in range(4, 2000, 2):
        t = shuffle_times(i)
        if t == n:
            print(f'{i}张牌洗{t}次会恢复原状')
            total += i
    return total

print(sum_s(8))
print(sum_s(10))

运行结果表明，终止条件设置为 (2^n) 可能更合适，但原始算法效率较低。

第四步：优化算法

观察洗牌过程中数字1的位置变化，发现只需跟踪数字1的位置即可。修改算法，通过整数运算代替列表操作，显著提高了效率。

def shuffle_pos(n, i):
    pos = i * 2
    if pos >= n:
        pos -= n - 1
    return pos

def shuffle_times(n):
    pos = 1
    pos = shuffle_pos(n, pos);
    count = 1
    while pos != 1:
        pos = shuffle_pos(n, pos)
        count += 1
    return count

assert shuffle_times(2) == 1
assert shuffle_times(52) == 8
assert shuffle_times(86) == 8

def sum_s(n):
    total = 0
    for i in range(4, 2**n+1, 2):
        t = shuffle_times(i)
        if t == n:
            print(f'{i}张牌洗{t}次会恢复原状')
            total += i
    return total

assert sum_s(8) == 412
assert sum_s(10) == 1506
print(sum_s(16))

第五步：进一步优化算法

通过数学分析发现，如果 (n) 张牌需要 (60) 次洗牌才能恢复原状，则 ((2^{60} - 1)) 必须能被 ((n-1)) 整除。因此，问题转化为寻找 ((2^{60} - 1)) 的所有因子。

from primePy import primes

def sum_s(n):
    p = 2 ** n - 1
    facs = primes.factors(p)
    all_factors = set()
    for i in range(2**len(facs)):
        s = f'{i+1:0{len(facs)}b}'
        prod = 1
        for j, ch in enumerate(s):
            if ch == '1':
                prod *= facs[j]
        all_factors.add(prod + 1)
    total = 0
    for i in all_factors:
        t = shuffle_times(i)
        if t == n:
            total += i
    return total

assert sum_s(8) == 412
assert sum_s(10) == 1506
assert sum_s(12) == 8628
assert sum_s(14) == 22402
print(sum_s(60))

最终答案为：