程序員的算法趣題Q50: 完美洗牌

xeblog 發(fā)布于2021-10-11 10:58 / 3169人閱讀

摘要：的結(jié)果與原書的結(jié)果不符。上一篇程序員的算法趣題欲速則不達程序員的算法趣題欲速則不達下一篇程序員的算法趣題同時結(jié)束的沙漏本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解

1. 問題描述

1. 問題描述

????????問題：對2n張牌洗牌，并求當(dāng)1<=n<=100時，一共有多少個n可以使得經(jīng)過2(n-1)次洗牌后，恢復(fù)最初順序？分兩種情況考慮：

????????Case1: 2(n-1)次洗牌后，牌恢復(fù)最初順序

????????Case2: 2(n-1)次洗牌后第一次恢復(fù)順序

????????Case2可以看作是case1的一種特殊情況。Case1的意思是，如果在m{其中m為2(n-1)的因子}次洗牌后回復(fù)最初順序即可。

?2. 解題分析

2.1 思路1

????????第一感是以下這個‘高大上’的想法：

????????呃。。。雖說如此，群論只學(xué)了一丟丟。。。等我先把群論學(xué)一學(xué)再來看這條路能不能走通。本系列其實出現(xiàn)過好幾道可以用群論來解決的問題。群論學(xué)習(xí)從開始到放棄經(jīng)歷過好多次了，這次帶著問題去學(xué)習(xí)看看能不能走得遠一些。?

2.2 思路2

????????（沒有別的更炫的法子時）蠻干就是了。。。

????????針對每一個n，從初始狀態(tài)（初始狀態(tài)是什么并不重要）開始，以迭代的方式進行以上permutation操作，并判斷是否回到了最初狀態(tài)。

????????算法流程如下：

3. 代碼及測試

# -*- coding: utf-8 -*-"""Created on Sat Oct  9 19:33:11 2021@author: chenxy"""# import sysimport time# import datetime# import math# import random# from   typing import List# from   queue import Queue# from   collections import deque# import itertools as itimport numpy as npN = 100ok_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運行結(jié)果：

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運行結(jié)果（注釋掉 "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的結(jié)果與原書的結(jié)果不符。想不出哪里不對，哪個小伙伴看出來毛病來了請不吝指教^-^