程序员的算法趣题Q50: 完美洗牌

目录

1. 问题描述

 2. 解题分析

2.1 思路1

2.2 思路2

3. 代码及测试

4. 后记


1. 问题描述

程序员的算法趣题Q50: 完美洗牌

程序员的算法趣题Q50: 完美洗牌

 

        问题:对2n张牌洗牌,并求当1<=n<=100时,一共有多少个n可以使得经过2(n-1)次洗牌后,恢复最初顺序?分两种情况考虑:

        Case1: 2(n-1)次洗牌后,牌恢复最初顺序

        Case2: 2(n-1)次洗牌后第一次恢复顺序

        Case2可以看作是case1的一种特殊情况。Case1的意思是,如果在m{其中m为2(n-1)的因子}次洗牌后回复最初顺序即可。

 2. 解题分析

2.1 思路1

        第一感是以下这个‘高大上’的想法:

程序员的算法趣题Q50: 完美洗牌

        呃。。。虽说如此,群论只学了一丢丢。。。等我先把群论学一学再来看这条路能不能走通。本系列其实出现过好几道可以用群论来解决的问题。群论学习从开始到放弃经历过好多次了,这次带着问题去学习看看能不能走得远一些。 

 

2.2 思路2

        (没有别的更炫的法子时)蛮干就是了。。。

        针对每一个n,从初始状态(初始状态是什么并不重要)开始,以迭代的方式进行以上permutation操作,并判断是否回到了最初状态。

        算法流程如下:

程序员的算法趣题Q50: 完美洗牌

 

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sat Oct  9 19:33:11 2021

@author: chenxy
"""

# import sys
import time
# import datetime
# import math
# import random
# from   typing import List
# from   queue import Queue
# from   collections import deque
# import itertools as it
import numpy as np

N = 100

ok_list = []

tStart = time.perf_counter()
for n in range(1,N+1):
    start = np.arange(2*n)
    p     = np.zeros_like(start)
    for k in range(n):
        p[2*k]   = start[k]
        p[2*k+1] = start[n+k]
    # print(p)
    
    cur = start
    cnt = 0
    # recover = False
    while 1:
        cur = cur[p]
        cnt = cnt + 1
        if np.array_equal(cur, start):
            # print(n, cur, start, cnt)
            if (2*(n-1) % cnt) == 0:
            # if (2*(n-1)) == cnt:
                # print(n, cur, start, cnt)
                # recover = True
                ok_list.append(n)
                break
        if cnt > 2*(n-1):
            break
    # if recover:
        # ok_list.append(n)
tCost  = time.perf_counter() - tStart
        
print('length of ok_list = {0}, tCost = {1:6.3f}(sec)'.format(len(ok_list),tCost))
print(ok_list)        
    

case1运行结果:

length of ok_list = 46, tCost =  0.046(sec)
[1, 2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, 51, 52, 54, 55, 57, 64, 66, 69, 70, 75, 76, 79, 82, 84, 87, 90, 91, 96, 97, 99, 100]

case2运行结果(注释掉 "if (2*(n-1) % cnt) == 0:",打开 “ if (2*(n-1)) == cnt:)":

length of ok_list = 45, tCost =  0.059(sec)
[2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, 51, 52, 54, 55, 57, 64, 66, 69, 70, 75, 76, 79, 82, 84, 87, 90, 91, 96, 97, 99, 100]

        尴尬。。。case2的结果与原书的结果不符。想不出哪里不对,哪个小伙伴看出来毛病来了请不吝指教^-^

4. 后记

        两个遗留事项:

        (1) 基于群论的解决方法

        (2) case2的结果不对

        嗯,我一定会回来的。。。

        上一篇:程序员的算法趣题Q49: 欲速则不达

        本系列总目录参见:程序员的算法趣题:详细分析和Python全解

上一篇:【小记】go如何判断key是否在map中


下一篇:2021-10-13 JavaScript编程练习