程序员的算法趣题Q42: 将牌洗为逆序

1. 问题描述

本题来自《程序员的算法趣题》中的第42题。

假设有2n张扑克牌，每次我们从中抽取n张牌（不是分散地抽取，而是抽取连续的一沓牌）放置到牌堆的顶上。然后重复这个操作，直到牌的顺序和最初顺序相反。

请问，当n=5时，要使10张牌逆序排列最少需要经过多少步？

2. 分析

N=1. 显然只需要1次操作就能将排序颠倒。

N=2. 假定初始序为[1,2,3,4]，假定左边表示在排队上面的位置。则可以通过以下操作步骤将原排序颠倒：[1,2,3,4]à[2,3,1,4]à[3,1,2,4]à[2,4,3,1]à[4,3,2,1]，即4次操作可以将原排序颠倒（参见以下附图1）。但是，能证明4次是最少需要的次数吗？

N=3的情况要仅靠纸和笔来计算出来已经超出了一般人的大脑承受范围了。

牌堆的每一种排序代表一种状态，当有2N张牌时有(2N)!种状态。当N=3时，状态数已经增长至(6!)=720了，所以用手算的方式求解几乎不可能了。

问题可以转化为从初始状态（不失一般性可以记为[1,2,3,…,2*N]）通过题目所约定的操作到达终止状态[2*N,2*N-1,…,3,2,1]所需要的最小步数。这其实也就是图的两个节点之间的最短距离的问题。解决这个最短距离问题的“标准”算法是广度优先搜索（BFS: Breadth First Search）。

广度优先搜索的几个要素：

1. 状态表示。本题中可以用2*N个数的一个排列来表示一种状态，为了计算给出最短距离，还需要记录某个状态与初始状态的距离。
2. 状态之间的转移，或者说求一个节点的邻节点。在本题中，从每一种排列出发总共有N种抽取连续N张牌的方式，每种抽取方式得到一种新的状态。因此每个节点有N个邻节点。
3. 已访问节点的记忆。这是为了避免重复访问已经访问过的节点。

3. 广度优先搜索基本实现

图1 (上)N=2时的移动步骤；(下)广度优先搜索基本实现的伪代码

实现代码如下所示：

"""
Created on Wed Aug  4 09:06:49 2021

@author: chenxy
"""
import sys
import time
import random
from   typing import List
from   queue import Queue

class Solution:
    def reverseCardSet(self, N: int) -> List:
        stateQue = Queue(maxsize = 0) # an infinite queue for storing card set state
        distQue  = Queue(maxsize = 0) # an infinite queue for storing distance of each corresponding state
        
        s_start  = [k for k in range(1,2*N+1)]
        s_end    = [k for k in range(2*N,0,-1)]
        # print('s_start = ', s_start)
        # print('s_end = ', s_end)
        distQue.put(0)
        stateQue.put(s_start)
        visited = []
        
        while not stateQue.empty():
            curState = stateQue.get()
            curDist  = distQue.get()
            visited.append(curState)
            # print('curState: ',curState)
            if curState == s_end:
                return [curDist,len(visited)]
            else:                
                for k in range(1,N+1):
                    childState = curState[k:k+N] + curState[0:k] + curState[k+N:]
                    # print('    childState: ',childState)
                    if childState not in visited:
                        distQue.put(curDist+1)
                        stateQue.put(childState)

用以下代码进行测试：

if __name__ == '__main__':        
            
    sln = Solution()

    for N in range(1,5):
    # for N in range(2,3):    
        tStart = time.time()
        ans = sln.reverseCardSet(N)
        tCost = time.time() - tStart
        print('N = {0}, ans = {1}, tCost = {2}(sec)'.format(N, ans, tCost)) 

运行结果：

N = 1, ans = [1, 2], tCost = 0.0(sec)
N = 2, ans = [4, 11], tCost = 0.0(sec)
N = 3, ans = [7, 841], tCost = 0.029889583587646484(sec)
N = 4, ans = [8, 28889], tCost = 29.551127672195435(sec)

ANS的第一项代表所需要的步骤数，而第二项代表所访问过的节点或者状态数。

结果分析：

N=4的耗时相比N=3增长了约1000倍！定性分析的话，一方面是所需要访问节点/状态数大幅度增长了；另一方面，每个状态的表示长度也从6变为8，因此单次存取和状态比较的时间也变大了。但是这个似乎不能完全解释1000倍的比例。

按照这个增长速度往下走的话，很显然N=5的运行计算将会变得难以忍受的长。需要从两个方面考虑优化：（1）算法的优化；（2）实现方式的优化，比如说存储中间数据的存储数据结构等的优化。

另外，N=3时，总共只有(2*N)=720种节点状态，为什么访问节点状态数会达到841？这是不是意味着当前的基本实现本身还存在bug？

4. Bug-fix and Optimization

4.1 When to update visited?

在深度优先搜索的非递归实现中，一个容易犯错误的坑是更新visited的时机。

在以上实现中，在出栈的时候将从栈中取出的节点（状态）加入到visited，而这正是导致总的访问节点状态数竟然超过了总的可能状态数的情况。实际上应该在入栈的时候就同时加入到visited中去。在算法教科书中这一点肯定在算法流程介绍中已经列出来了，但是由于显得那么理所当然其实并不一定会注意到这个细节或者想到为什么要这样做呢？只有在实际实现中碰到这个问题并且踩过坑才会认真地思考为什么。以下简要解释一下。

在广度优先搜索中，节点是分层的，每一层在栈中挤在一起。考虑当前层的节点有N1,N2,…,Nk，在从栈中依此读出N1,N2,…,Nk处理并将下一层的节点M1,M2,…,Mx时需要判断它们是不是visited过。存在这样的可能，比如说，N1的邻(或子)节点有与N2,…Nk重叠的，这样就会如果是在出栈时才加入到visited中的话，那么这个子节点就会被再次加入到visited，从而造成重复。

4.2What to implement visited

Visited需要进行大量的查询。在初始实现中是采用list来实现的。

在python中，dict()的查询要远远地快于list的查询。

用dict()替换list实现visited后，运行速度提高了接近三个数量级！

当然，初始实现中节点状态是用list表示的，而dict不接收list作为key，所以优化实现中改为用tuple来表示状态。

4.3 Quere vs deque?

用collections.deque替换queue.Queue后，运行速度也得到了一定的提高(大概效率提高了1倍？)

5. 优化实现：代码及测试

    def reverseCardSet2(self, N: int) -> List:
        stateQue = deque() # Using deque is faster than Queue.
        distQue  = deque()
        
        s_start  = tuple([k for k in range(1,2*N+1)])
        s_end    = tuple([k for k in range(2*N,0,-1)])
        # print('s_start = ', s_start)
        # print('s_end = ', s_end)
        distQue.append(0)
        stateQue.append(s_start)
        visited = dict()
        visited[s_start] = ''
        
        while len(stateQue) > 0:
            curState = stateQue.popleft()
            curDist  = distQue.popleft()
            # visited.append(curState)
            # print('curState: ',curState)
            if curState == s_end:
                return [curDist,len(visited)]
            else:                
                for k in range(1,N+1):
                    childState = curState[k:k+N] + curState[0:k] + curState[k+N:]
                    # print('    childState: ',childState)
                    if childState not in visited:
                        distQue.append(curDist+1)
                        stateQue.append(childState)
                        visited[childState] = ''

N = 3, ans = [7, 709], tCost = 0.0009953975677490234(sec)

N = 4, ans = [8, 19989], tCost = 0.04089236259460449(sec)

N = 5, ans = [12, 3628799], tCost = 14.644261837005615(sec)

这个结果虽然比初始实现版本快近三个数量级，仍然不能让人满意。N=5时耗时15秒左右，按照这个速度下去，N=6耗时将会漫长得无法忍受。

革命尚未成功，优化还需继续！