首頁猿問使用python中的特定規則集生成...

使用python中的特定規則集生成電話號碼

Python

慕碼人8056858 2021-09-11 19:19:14

我想編寫一個函數，它使用以下規則集從標準電話鍵盤（圖 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,:])

反對回復 2021-09-11

蕪湖不蕪

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)

反對回復 2021-09-11

2 回答
0 關注
290 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

使用python中的特定規則集生成電話號碼

使用python中的特定規則集生成電話號碼

2 回答

序幕

表示

添加回答