程序员的算法趣题Q56: 鬼脚图中的横线(思路2的Python题解)

admin • 2021-11-18 20:07 • 程序人生

1. 问题描述

问题描述以及此前的讨论参见：

程序员的算法趣题Q56: 鬼脚图中的横线(思路1)https://blog.csdn.net/chenxy_bwave/article/details/121156166https://blog.csdn.net/chenxy_bwave/article/details/121156166 程序员的算法趣题Q56: 鬼脚图中的横线（思路2）https://blog.csdn.net/chenxy_bwave/article/details/121212455https://blog.csdn.net/chenxy_bwave/article/details/121212455

本文给出对应于以上思路2的正式的python题解。虽然前面所提出的问题（比如说，原问题与变换后的问题是否是等价的呢，如何证明？）没有解决，但是我猜测这里所做的问题转换是正确的，姑且先不管它在数学意义上的严谨证明，先把它实现了再说了。

2. 实现方案

如前所述，问题转变成了上面一排数字和下面一排数字（相同数字之间）连线后总的交叉点的个数的问题。

考虑上面一排中数字{1,2,3,...,N}的位置是(x1,x2,...,xN)—当然由于上面这一排是初始排列所以有xk=k；下面一排数字的位置是(y1,y2,...,yN)，很显然，(y1,y2,...,yN)也是{1,2,3,...,N}的一个排列。在python中可以用itertools.permutations()来生成所有N个数的排列。

针对下面一排的每一种可能的排列，将对应数字相同的两点连接起来，得到N根连线，每根连线用(xi,yi)表示，xi表示线段一端在上面一排的位置，yi表示线段一端在下面一排的位置。

接下来就是判断两根线段是否相交的问题了。有一个很简单的判断方法，如果两根线段的一段在上面一排中的相对位置与它们的另一端在下面一排中的相对位置不同的话，即表示它们相交。以数学的方式表示就是：

示意图如下，图中两根线段的位置坐标分别为(2,3)和(3,1)，它们在图中也的确是相交的，它们的坐标满足上式的关系。

据此可以得到本题的算法流程：

3. 代码实现

# -*- coding: utf-8 -*-
"""
Created on Sun Nov 14 13:57:51 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 = 7
cnt_geq_10 = 0
tStart = time.perf_counter()
for pItem in it.permutations(range(1,N+1)):
    # print(pItem)
    lines = []
    for i in range(1,N+1):
        lines.append((i,pItem.index(i)+1))
    
    num_crosspoints = 0
    for i in range(N-1):
        for j in range(i+1,N):
            x1,y1 = lines[i]
            x2,y2 = lines[j]
            if (x2-x1)*(y2-y1) < 0:
                num_crosspoints += 1    
    # if num_crosspItemoints >= 10:
    if num_crosspoints == 10:
        cnt_geq_10 += 1

tCost  = time.perf_counter() - tStart
print('N={0}, cnt_geq_10={1}, tCost = {2:6.3f}(sec)'.format(N,cnt_geq_10,tCost))

运行结果：N=7, cnt_geq_10=573, tCost = 0.051(sec)

不过要注意的是，原题说的是“最少需要10条横线的鬼脚图数”，但是最后给出的解573其实是“正好需要10条横线的鬼脚图数”。不过差异仅在于最后num_crosspoints“等于”10还是“大于等于10”而已。