程序员的算法趣题Q53: 同数包夹

时间：12-31来源：作者：点击数：

1. 问题描述

有分别标了数字1~n的两副牌，共2n张。把这些牌排成一排，确保两张1的中间夹一张牌，两张2的中间夹2张牌，。。。，两张n的中间夹n张牌。

请问，当n=11时，有多少种排列方法？

2. 解题分析

考虑有2n个位置，按顺序地且按照以上规则的约束，安放每个数字的两张牌，直到2n张牌将2n个位置占满。这样的话这个问题可以看成（转换成）图搜索问题中的路径遍历问题。即从“空”状态开始到达“满”状态的所有不同路径的数量。这可以通过深度优先搜索来解决。

但是要注意的是，这里的终止状态并不是唯一的，所有的“满”状态都是终止状态。所以这不是从图中的某个起始节点到另一终止节点之间的路径遍历，而是遍历搜索从“空”状态节点到达所有合法的“满”状态节点的可能路径。

深度优先路径遍历搜索的要点如下所述。

2.1 节点表示

以长度2n的数组表示，“空”状态指数组中的元素为全“0”。“满”状态指数组中的元素全部为非零的状态，但是并非所有的“满”状态都是合法的状态。但是在本题中单独的状态还不能完全表示一个节点，还要加上接下来要插入的数据才能足以唯一地表示节点信息，即{state, m}。

2.2 邻节点搜索

基于当前状态curState和接下来要插入的数据m，可以按如下方式确定邻节点：从数组头部开始搜索，搜索到两个相隔m个位置都为空的时候，即可认为找到一个合法的邻节点{newState, m+1}，newState为将m插入前述两个位置，而接下来要插入的数也相应地更新为m+1。

2.3 Memoization

3. 递归实现：从小到大插入

import sys
import time
# import random
# from   typing import List
# from   queue import Queue
# from   collections import deque

class Solution:
    def numberArrangement(self, N: int) -> int:
        """
        :N:    
        :ret:  The number of arrangement
        """        
        start   = 2*N*[0]    # Nested list to represent state/node
                                            
        def explore(curState, num):
            """
            :curState: current state to explore
            :num:     the number to be arranged
            :ret:     the number of arrangements
            """
            # print('explore({0}, {1})'.format(curState, num))
            # Judge whether reach the goal or final state.
            if num > N:
                return 1
            
            sum = 0
            for k in range(0,2*N-num-1):
                if curState[k]==0 and curState[k+num+1]==0:
                    # nxtState    = curState # Both points to the same object! NG
                    nxtState    = curState.copy()
                    nxtState[k] = num
                    nxtState[k+num+1] = num
                    sum += explore(nxtState,num+1)            
            return sum

        return explore(start,1)

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

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