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

2 回答

• 2

  序曲

  让我们说另一种解决你的问题的方法，它不涉及线性代数，但仍然依赖于图论 .

  代表

  您的问题的自然表示是图表，如下所示：

  并相当于：

  我们可以用字典来表示这个图：

  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 是another answer中定义的邻接矩阵 .

  递归

  现在我们可以使用递归生成所有电话号码：

  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
  

  然后我们 Build 电话号码列表：

  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版本 .

  基准

  Claim without proof: 递归函数的复杂性应该在 O(2^n) 和 O(3^n) 之间，因为递归树作为 n-1 的深度，每个内部节点创建最少2条边和最多3条边 . 这里的方法不是分而治之的组合字符串生成器 .

  对两个函数进行基准测试似乎证实了这一主张：

  递归函数以对数标度显示线性行为，其确认了指数复杂性并且如所述限制 . 更糟糕的是，除了计算之外，还需要越来越多的内存来存储列表（我无法获得比_27390更多的内容，然后我的笔记本电脑冻结了） .

  对于问题大小 n ，Matrix Power方法似乎有一个恒定的时间 . numpy.linalg.matrix_power上没有实现细节，但这是known eigenvalues problem . 因此，复杂性似乎在 n 之前是恒定的，因为矩阵形状独立于 n （它仍然是 10x10 矩阵）并且大部分计算时间即将解决特征值问题而不是将对角矩阵提升为 n th幂 . 该解决方案将需要准恒定量的存储器来存储矩阵及其分解，仅此而已 .

  回复于 2024-04-20T21:58:21+08:00
• 3

  功能签名

  该功能必须将电话号码和初始位置的长度作为输入，并且输出给出唯一电话号码的数量 .

  关键理念

  您的问题可以通过图论和线性代数来解决（这些学科遇到的一个有趣的地方是离散数学） .

  首先，我们创建一个Adjacency Matrix代表电话键盘上的合法移动：

  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 的唯一电话号码的数量）walks的数量（以数字 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.]]
  

  Matrix 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,:])
  

  该工作的大部分内容包括对Matrix进行编码，该Matrix描述了一组规则（允许在键盘上移动） .

  检查

  基于观察我们可以从问题描述中得出，比如@SpghttCd，我们可以检查从 2 开始，没有包含数字 5 的长度 10 的数量：

  W[2,5] # 0.0
  

  我们可以检查从 5 开始不能写入长度为 10 的数字：

  phoneNumbersCount(10, 5) # 0.0
  

  实际上，对于给定的规则集，数字 5 根本不可用 .

  我们还可以检查另一个不明显的属性，例如：没有 10 的长度 10 ，以 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)
  

  参考文献

  一些有用的参考，以了解它的工作原理和原因：

  • Kenneth H. Rosen ，离散数学及其应用，Mc Graw Hill，第7版，2012年（第688页，计算顶点之间的路径）;

  • http://www-users.math.umn.edu/~musiker/4707/Matrices.pdf

  • http://www.math.ucsd.edu/~gptesler/184a/slides/184a_ch10.3slides_17-handout.pdf

  • https://math.dartmouth.edu//archive/m68f11/public_html/algcomb.pdf

  回复于 2024-04-20T21:58:21+08:00