使用python中的特定规则集生成电话号码

序幕让我们陈述另一种解决问题的方法，该方法不涉及线性代数，但仍依赖于图论。表示您的问题的自然表示是如下所示的图表：并且相当于：我们可以用字典来表示这个图：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 AC = 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 timeitnr = 20ns = 100N = 15nt = np.arange(N) + 1t = 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,:])

使用python中的特定规则集生成电话号码

2回答