我想编写一个函数，它使用以下规则集从标准电话键盘（图 1）生成所有可能的数字：电话号码以数字 2 开头电话号码长度为 10 位每个电话号码中的连续数字是在国际象棋中的骑士移动时选择的在国际象棋中，骑士（有时称为马）垂直移动两步和水平移动一步或水平移动两步和垂直移动一步。电话号码中只能使用数字 - 即不允许使用 (#) 和 (*) 键。该函数必须将电话号码的长度和初始位置作为输入，并为输出提供唯一电话号码的数量。我是一个新手，面临着构建逻辑的困难。我尝试按照以下方式进行操作，这绝对不是正确的方法。def genNumbers(len, initpos):numb = list('2xxxxxxxxx')#index 1numb[1] = 7 or 9if numb[1] == 7: numb[2] == 2 or 6elif numb[1] == 9: numb[2] == 2 or 4#index 2if numb[2]== 2: numb[3] == 7 or 9elif numb[2]== 4: numb[3] == 3 or 9elif numb[2]== 6: numb[3] == 1 or 7#index 3if numb[3]== 1: numb[4] == 6 or 8 elif numb[3]== 3: numb[4] == 4 or 8 elif numb[3]== 7: numb[4] == 2 or 6 elif numb[3]== 9: numb[4] == 2 or 4 #index 4if numb[4] == 8: numb[5]== 1 or 3elif numb[4] == 2: numb[5]== 7 or 9elif numb[4] == 4: numb[5]== 3 or 9elif numb[4] == 6: numb[5]== 1 or 7#index 5if numb[5] == 1: numb[6]== 6 or 8elif numb[5] == 3: numb[6]== 4 or 8elif numb[5] == 7: numb[6]== 2 or 6 elif numb[5] == 9: numb[6]== 2 or 4#index 6 if numb[6] == 2: numb[7]== 7 or 9elif numb[6] == 4: numb[7]== 3 or 9 elif numb[6] == 6: numb[7]== 1 or 7elif numb[6] == 8: numb[7]== 1 or 3#index 7 if numb[7] == 1: numb[8]== 6 or 8elif numb[7] == 3: numb[8]== 4 or 8elif numb[7] == 7: numb[8]== 2 or 6 elif numb[7] == 9: numb[8]== 2 or 4#index 8if numb[8] == 6: numb[9]== 1 or 7elif numb[8] == 8: numb[9]== 1 or 3elif numb[8] == 4: numb[9]== 3 or 9elif numb[8] == 2: numb[9]== 7 or 9return numb任何帮助将不胜感激！
2 回答
三国纷争
TA贡献1804条经验 获得超7个赞
序幕
让我们陈述另一种解决问题的方法，该方法不涉及线性代数，但仍依赖于图论。
表示
您的问题的自然表示是如下所示的图表：
并且相当于：
我们可以用字典来表示这个图：
G = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [0, 3, 9],
5: [], # This vertex could be ignored because there is no edge linked to it
6: [0, 1, 7],
7: [2, 6],
8: [1, 3],
9: [2, 4],
}
这种结构将使您无需编写if语句。
邻接矩阵
上面的表示包含与邻接矩阵相同的信息。此外，我们可以从上面的结构生成它（将布尔稀疏矩阵转换为整数矩阵）：
def AdjacencyMatrix(d):
A = np.zeros([len(d)]*2)
for i in d:
for j in d[i]:
A[i,j] = 1
return A
C = AdjacencyMatrix(G)
np.allclose(A, C) # True
另一个答案中A定义的邻接矩阵在哪里。
递归
现在我们可以使用递归生成所有电话号码：
def phoneNumbers(n=10, i=2, G=G, number='', store=None):
if store is None:
store = list()
number += str(i)
if n > 1:
for j in G[i]:
phoneNumbers(n=n-1, i=j, G=G, number=number, store=store)
else:
store.append(number)
return store
然后我们建立电话号码列表：
plist = phoneNumbers(n=10, i=2)
它返回：
['2727272727',
'2727272729',
'2727272760',
'2727272761',
'2727272767',
...
'2949494927',
'2949494929',
'2949494940',
'2949494943',
'2949494949']
现在只是获取列表的长度：
len(plist) # 1424
检查
我们可以检查没有重复：
len(set(plist)) # 1424
我们可以检查比我们对另一个答案中最后一位数字所做的观察在这个版本中仍然成立：
d = set([int(n[-1]) for n in plist]) # {0, 1, 3, 7, 9}
电话号码不能以：
set(range(10)) - d # {2, 4, 5, 6, 8}
比较
这第二个答案：
不需要numpy（不需要线性代数），只使用 Python 标准库；
是否使用图形表示，因为它是您问题的自然表示；
在计算之前生成所有电话号码，之前的答案没有生成所有电话号码，我们只有表格中的数字详细信息x********y；
使用递归来解决问题，并且似乎具有指数时间复杂度，如果我们不需要生成电话号码，我们应该使用 Matrix Power 版本。
基准
递归函数的复杂性应该在O(2^n)和之间，O(3^n)因为递归树的深度为n-1（并且所有分支具有相同的深度）并且每个内部节点创建最少 2 条边，最多 3 条边。这里的方法不是分治算法，它是一个组合字符串生成器，这就是为什么我们期望复杂性是指数级的。
对两个函数进行基准测试似乎证实了这一说法：
递归函数在对数尺度上显示线性行为，这证实了指数复杂性，并且如所述有界。更糟糕的是，除了计算之外，它还需要越来越多的内存来存储列表。我不能再进一步了n=23，然后我的笔记本电脑在拥有MemoryError. 更好的复杂性估计是O((20/9)^n)基数等于顶点度数的平均值（不连接的顶点被忽略）。
Matrix Power 方法似乎对问题的大小有一个恒定的时间n。numpy.linalg.matrix_power文档中没有实现细节，但这是一个已知的特征值问题。因此我们可以解释为什么之前的复杂性似乎是恒定的n。这是因为矩阵形状独立于n（它仍然是一个10x10矩阵）。大部分计算时间都用于解决特征值问题，而不是将对角特征值矩阵提升到 n 次方，这是一个微不足道的操作（并且唯一依赖于n）。这就是为什么此解决方案以“恒定时间”执行的原因。此外，它还需要准恒定量的内存来存储矩阵及其分解，但这也与 无关n。
奖金
在下面找到用于基准函数的代码：
import timeit
nr = 20
ns = 100
N = 15
nt = np.arange(N) + 1
t = np.full((N, 4), np.nan)
for (i, n) in enumerate(nt):
t[i,0] = np.mean(timeit.Timer("phoneNumbersCount(n=%d)" % n, setup="from __main__ import phoneNumbersCount").repeat(nr, number=ns))
t[i,1] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=2))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
t[i,2] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=0))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
t[i,3] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=6))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
print(n, t[i,:])
芜湖不芜
TA贡献1796条经验 获得超7个赞
函数签名
该函数必须将电话号码的长度和初始位置作为输入，并为输出提供唯一电话号码的数量。
核心理念
你的问题可以通过图论和线性代数来解决（这些学科交汇的一个有趣的地方是离散数学）。
首先，我们创建一个表示手机键盘上合法移动的邻接矩阵：
import numpy as np
A = np.zeros((10, 10))
A[0,4]=1
A[0,6]=1
A[1,6]=1
A[1,8]=1
A[2,7]=1
A[2,9]=1
A[3,4]=1
A[3,8]=1
A[4,0]=1
A[4,3]=1
A[4,9]=1
A[6,0]=1
A[6,1]=1
A[6,7]=1
A[7,2]=1
A[7,6]=1
A[8,1]=1
A[8,3]=1
A[9,2]=1
A[9,4]=1
我们可以检查矩阵是否对称（不是必需的，但它是系统的一个属性）：
np.allclose(A, A.T) # True
邻接矩阵的输入是这样的：A[0,4]=1意味着从顶点移动0到顶点4，A[0,5]=0意味着没有移动0到5。
[[0. 0. 0. 0. 1. 0. 1. 0. 0. 0.]
[0. 0. 0. 0. 0. 0. 1. 0. 1. 0.]
[0. 0. 0. 0. 0. 0. 0. 1. 0. 1.]
[0. 0. 0. 0. 1. 0. 0. 0. 1. 0.]
[1. 0. 0. 1. 0. 0. 0. 0. 0. 1.]
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[1. 1. 0. 0. 0. 0. 0. 1. 0. 0.]
[0. 0. 1. 0. 0. 0. 1. 0. 0. 0.]
[0. 1. 0. 1. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 1. 0. 0. 0. 0. 0.]]
然后我们计算A提出在电源9这给我们的数量阶层的长度9（这相当于长度的唯一的电话号码数10）两个给定顶点（从数字之间x以及与数字结尾y）：
W = np.linalg.matrix_power(A, 9)
路径长度是n-1因为顶点是数字，边是键盘上的移动，因此要拨打10-digits 电话号码，您需要9移动（长度的步行9）。
它给了我们：
[[ 0. 0. 336. 0. 544. 0. 544. 0. 336. 0.]
[ 0. 0. 264. 0. 432. 0. 448. 0. 280. 0.]
[336. 264. 0. 264. 0. 0. 0. 280. 0. 280.]
[ 0. 0. 264. 0. 448. 0. 432. 0. 280. 0.]
[544. 432. 0. 448. 0. 0. 0. 432. 0. 448.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[544. 448. 0. 432. 0. 0. 0. 448. 0. 432.]
[ 0. 0. 280. 0. 432. 0. 448. 0. 264. 0.]
[336. 280. 0. 280. 0. 0. 0. 264. 0. 264.]
[ 0. 0. 280. 0. 448. 0. 432. 0. 264. 0.]]
矩阵W条目读作：W[2,1] = 264表示存在264长度以10开头2和结尾的电话号码1。
现在我们总结从顶点开始的步行2：
np.sum(W[2,:]) # 1424.0
有1424长度的电话号码10开头数字2为一组您所提供的规则。
功能
这个函数很容易写：
def phoneNumbersCount(n=10, i=2, A=A):
return np.sum(np.linalg.matrix_power(A, n-1)[i,:])
大部分工作包括对描述规则集（键盘上允许的移动）的矩阵进行编码。
检查
根据我们可以从问题描述中得出的观察结果，例如@SpghttCd 所做的，我们可以检查是否没有10从2包含数字开始的长度数5：
W[2,5] # 0.0
我们可以检查是否10可以从5以下位置开始写入任何长度：
phoneNumbersCount(10, 5) # 0.0
实际上5，对于给定的规则集，数字根本不可用。
我们还可以查看其他性质并不明显，例如：没有号码长度的10开始2和结束或者2，4，5，6或8：
W[2,:] # [336. 264. 0. 264. 0. 0. 0. 280. 0. 280.]
暗示
因为图没有方向（每条边都存在于两个方向），所以邻接矩阵是对称的。因此，矩阵创建可以简化为：
B = np.zeros((10, 10))
B[0,4]=1
B[0,6]=1
B[1,6]=1
B[1,8]=1
B[2,7]=1
B[2,9]=1
B[3,4]=1
B[3,8]=1
B[4,9]=1
B[6,7]=1
B = np.maximum(B, B.T)
添加回答
举报
0/150
提交
取消