程序员的算法趣题Q25: 时髦的鞋带系法

1. 问题描述

即便系得很紧，鞋带有时候还是免不了会松掉。运动鞋的鞋带有很多时髦的系法。下面看看这些系法里，鞋带是如何穿过一个又一个鞋带孔的。如下图所示的这几种依次穿过 12个鞋带孔的系法很有名（这里不考虑鞋带穿过鞋带孔时是自外而内还是自内而外）。

这里指定鞋带最终打结固定的位置如上图中的前两种系法所示，即固定在最上方（靠近脚腕）的鞋带孔上，并交错使用左右的鞋带孔。

问题：鞋带交叉点最多时的交叉点个数。譬如上图左侧的系法是 5个，正中间的系法是9个。

2. 解题分析

深度优先路径遍历问题。

本系列中已经出现过很多类似问题，比如Q24, Q23, Q18, Q14, just to name a few. 此类问题都可以直接套用类似的框架套路，除了一些problem-specific的细节需要针对个别问题具体处理，比如说，如何进行状态表示，如何给出下一个状态的遍历列表，等等。

本文在路径遍历的基础上进一步要求找出各种系法（即各种路径）中的交叉点数，而不仅仅是给出可能的路径数，这就要求（1）在路径遍历的同时要记住每条路径的历史；（2）对每条路径中的交叉点进行数数。

由于要记住每条路径的历史，所以memoization技巧不能用了（待确认）.

2.1 状态表示方法

考虑用left和right两个列表来表示当前状态，分别表示左右两列剩下的鞋带孔。由于鞋带孔不能重复穿过，基于这种表示方法，在深度搜索过程中也免去了“是否已经访问过”的判断。

除此之外，还需要:

1. 指明下次应该轮到穿哪一列。activeCol: 0—left column; 1—right column
2. 上一次穿过的是哪个孔：lastPole

必须从左列第一个孔开始（从右列开始结果一样，假定这种对称的系法算同一种系法），而且最后一个必须是右列第一个孔，因此初始状态为：

left = [1,2,3,4,5], right=[1,2,3,4,5], activeCol=1, lastPole=0

右端最后一个孔是确定性的，因此在深度优先搜索中不进行处理(因此以上right中不包括0)，但是在搜索到终点进行交叉点计数时要把最后穿过right-pole-0的edge加入pathHist（参加下一节流程）。

2.2 DFS

2.3 遍历下一个状态

在问题中即寻找可以下一个穿过的鞋带孔。这里需要分从左到右和从右到左的处理，activeCol即为此目的而设。activeCol为1表示接下来是要从左到右；activeCol为0表示接下来是要从右到左。另外，还需要知道上一次穿过的孔（即lastPole），这样才能决定从哪个孔到哪个孔。

2.4 交叉判断

简单地来说，每个edge由两个数(x,y)决定，x是左边鞋带孔位置，y是右边鞋带孔位置。两个edges的x坐标的相对大小和y坐标的相对大小关系是反的的话，则表示交叉。参见isCross()。

3. 代码

# -*- coding: utf-8 -*-
"""
Created on Sun Sep 12 13:54:43 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

maxNumCross = 0
maxPath     = []

def isCross(edge1, edge2)->int:
    """
    Judge whether two edges cross

    Parameters
    ----------
    edge1 : tuple, (x,y)
        x represents the line number in left column
        y represents the line number in righg column
    edge2 : Same as edge1

    Returns: int. 0: not cross, 1: cross
    -------
    """
    if (edge1[0] - edge2[0]) * (edge1[1] - edge2[1]) < 0:
        return 1
    else:
        return 0

def explore(left:List, right:List, activeCol:int, lastPole:int, pathHist:List)->int:
    """
    Explore the total number of paths under the condition of "left" and "right", which
    contains the left poles in the left and right column, repectively.
    
    Parameters
    ----------
    left :  List. The left poles in the left column        
    right : List. The left poles in the right column                
    activeCol: int, indicate which column should be used in the next step. 0: left, 1, right
    Returns
    -------
    int:    The total number of paths traversing all the poles in interleaving way.
    """
    global maxNumCross
    global maxPath
    if len(left)==0 and len(right)==0:
        # find one path, and count the number of crosses
        # Firstly, add the last edge from lastPole to the first pole of right pole
        pathHist.append([lastPole,0])        
        numCross = 0
        for edges in it.combinations(pathHist, 2):
            edge1 = edges[0]
            edge2 = edges[1]
            numCross += isCross(edge1,edge2)        
        if numCross > maxNumCross:
            maxNumCross = numCross
            maxPath = pathHist.copy()
        pathHist.remove([lastPole,0])
        return 1
    
    count = 0
    if activeCol == 0:
        nxtActiveCol = 1
        for pole in left:
            nxtLeft = left.copy()
            nxtLeft.remove(pole)
            pathHist.append([pole,lastPole])
            count += explore(nxtLeft,right,nxtActiveCol,pole,pathHist)
            pathHist.remove([pole,lastPole])
    else:
        nxtActiveCol = 0
        for pole in right:
            nxtRight = right.copy()
            nxtRight.remove(pole)
            pathHist.append([lastPole,pole])
            count += explore(left,nxtRight,nxtActiveCol,pole,pathHist)        
            pathHist.remove([lastPole,pole])
            
    return count

if __name__ == '__main__':        
    
    # tStart  = time.perf_counter()
    # print(explore([1],[1],1,0,[]))            
    # tCost   = time.perf_counter() - tStart
    # print('Number of cross = {0}, tCost = {1:6.3f}(sec)'.format(maxNumCross, tCost))
    # print(maxPath)
    
    tStart  = time.perf_counter()
    print(explore([1,2,3,4,5],[1,2,3,4,5],1,0,[]))            
    tCost   = time.perf_counter() - tStart
    print('Number of cross = {0}, tCost = {1:6.3f}(sec)'.format(maxNumCross, tCost))
    print(maxPath)

运行结果：

14400

Number of cross = 45, tCost = 0.300(sec)

[[0, 5], [1, 5], [1, 4], [2, 4], [2, 3], [3, 3], [3, 2], [4, 2], [4, 1], [5, 1], [5, 0]]

第一个数字是可能系法总数，最后一个结果是具有最大交叉点的系法的鞋带孔穿越顺序。

4. 后记

其实，总的可能系法总数可以很简单地直接计算出来，即。理由就留给小伙伴们自己思考了。本题中因为要给具体的路径历史（即鞋带孔穿越顺序），所以必须做穷尽的搜索。但是能直接计算出以上总的可能路径总数，对于程序调试是有帮助的。