我想知道我在python下面寫的演算法是否正確。
我的目標是找到一種演算法，可以列印/查找可以使用字符“！”中的字符完成的所有可能的單詞組合。（十進制值 = 33）到 asccii 表中的字符“~”（十進制值 = 126）：
這里使用遞回的代碼：
byteWord = bytearray(b'\x20') # Hex = '\x21' & Dec = '33' & Char = '!'
cntVerif = 0 # Test-------------------------------------------------------------------------------------------------------
def comb_fct(bytes_arr, cnt: int):
global cntVerif # Test------------------------------------------------------------------------------------------------
if len(bytes_arr) > 3: # Test-----------------------------------------------------------------------------------------
print(f'{cntVerif 1}:TEST END')
sys.exit()
if bytes_arr[cnt] == 126:
if cnt == len(bytes_arr) or len(bytes_arr) == 1:
bytes_arr.insert(0, 32)
bytes_arr[cnt] = 32
cnt = 1
cntVerif = 1 # Test----------------------------------------------------------------------------------------------
print(f'{cntVerif}:if bytes_arr[cnt] == 126: \n\tbytes_arr = {bytes_arr}') # Test-------------------------------------------------------------------------------------------
comb_fct(bytes_arr, cnt)
if cnt == -1 or cnt == len(bytes_arr)-1:
bytes_arr[cnt] = bytes_arr[cnt] 1
cntVerif = 1 # Test----------------------------------------------------------------------------------------------
print(f'{cntVerif}:if cnt==-1: \n\tbytes_arr = {bytes_arr}') # Test-------------------------------------------------------------------------------------------
comb_fct(bytes_arr, cnt=-1) # index = -1 means last index
bytes_arr[cnt] = bytes_arr[cnt] 1
cntVerif = 1 # Test--------------------------------------------------------------------------------------------------
print(f'{cntVerif}:None if: \n\tbytes_arr={bytes_arr}') # Test-----------------------------------------------------------------------------------------------
comb_fct(bytes_arr, cnt 1)
comb_fct(byteWord, -1)
感謝您的幫助，因為 python 只允許有限數量的遞回（在我的計算機上為 996）所以我例如我無法驗證我的演算法是否給出了所有長度為 3 的單詞，這些單詞可以通過字符描述的范圍來實作.
當然，如果有人有更好的想法來撰寫這個演算法（例如更快的演算法）。我會很高興閱讀它。
uj5u.com熱心網友回復：
盡管您可能可以對此進行一些調整，但我認為下面的代碼接近解決您的問題的最有效解決方案，我認為它是“從給定的字符集中生成所有可能的最大長度為N的序列”。這可能比您需要的更通用，因為您的字符集是固定的，但通用解決方案更有用，并且增加的開銷很小。
請注意，該函式是作為生成器撰寫的，使用itertools標準庫模塊中的函式。Itertools 被描述為一組“為高效回圈創建迭代器的函式”（強調添加），確實如此。生成器是 Python 的強大功能之一，因為它們允許您輕松有效地迭代復雜的序列。如果您想撰寫高效且“pythonic”的代碼，您應該熟悉這些概念（以及其他基本功能，例如理解）。所以我不打算進一步解釋這些特性；請閱讀教程部分了解詳細資訊。
所以這是一個簡單的解決方案：
from itertools import product, chain
def genseq(maxlen, chars):
return map(''.join,
chain.from_iterable(product(chars, repeat=i)
for i in range(maxlen 1)))
# Example usage:
chars = ''.join(chr(i) for i in range(33, 127))
for word in genseq(4, chars):
# Do something with word
有 78,914,411 個可能的詞（包括空詞）；以上在我的筆記本電腦上在 7 秒內生成所有這些。大部分時間都花在創建（和垃圾收集）這些字串上。您可能會更好地使用 abytearray并為每個生成的單詞回收它。我沒試過。
作為記錄，這是一種“取消索引”此類字串列舉的更簡單方法。列舉以空詞開始，然后是所有 1 個字符的詞，然后是 2 個字符的詞，依此類推。這種排序使得不必指定結果字串的長度（甚至最大長度）。
def unindex(i, chars):
v = []
n = len(chars)
while i > 0:
i -= 1
v.append(i % n)
i //= n
return ''.join(chars[j] for j in v[::-1])
# Example to generate the same words as above:
# chars as above
index_limit = (len(chars) ** 5 - 1) // (len(chars) - 1)
for i in range(0, index_limit):
word = unindex(i, chars)
# Do something with word
同樣，您可以通過使用回收的位元組陣列來加快速度。如上所述，它花了大約兩分鐘，是我第一個版本的十六倍。
請注意，以您在答案中的方式使用位元組陣列并不會顯著加快速度，因為它每次都會創建一個新的位元組陣列。為了實作節省，您必須在整個世代中使用單個位元組陣列，修改它而不是重新創建它。這在實踐中更尷尬，因為這意味著如果您需要保留生成的單詞以供以后使用，也許是因為它通過了一些測驗，您必須復制它。很容易忘記這一點，并且由此產生的錯誤可能很難追蹤。
uj5u.com熱心網友回復：
這里不需要遞回。將您的單詞視為n-digit 數字，其中數字是感興趣范圍內的 ASCII 符號 ( [!..~])。從最小的 (all !) 開始，然后將其遞增 1，直到達到最大 (all ~)。
要增加長數字，請將最低有效位元組加 1。如果它變成~，請制作!并嘗試增加下一個，等等。
請記住，單詞的數量是巨大的。有94 ** nn個字母的單詞。因為n == 4有 78074896 個。
uj5u.com熱心網友回復：
為了解決這個問題，我認為我找到了一種優雅且更快的方法來解決這個問題，而無需使用遞回演算法。我也認為這是時間最優解決方案（因為它是 O(n)）
我使用的事實是它在十進制的所有數字和以 94 為底的數字之間存在雙射。
很明顯，每個數字在base 94 可以使用唯一字符的特殊序列作為 ascii 代碼中 [30, 126] （十進制值）范圍內的字符寫入。
如果有人能確認我的解決方案是正確的，我會很高興。:-)
版本 1：
如果您對獲取表單的所有單詞不感興趣，例如長度為 2，“！R”（在我們的基礎中，“！”等于零。
# Get all ascii relevant character in a list
asciiList = []
for c in (chr(i) for i in range(33, 127)):
asciiList.append(c)
print(f'ascii List: \n{asciiList} \nlist length: {len(asciiList)}')
def base10_to_base94_fct(int_to_convert: int) -> str:
sol_str = ''
loop_condition = True
while loop_condition is True:
quo = int_to_convert // 94
mod = int_to_convert % 94
sol_str = asciiList[mod] sol_str
int_to_convert = quo
if quo == 0:
loop_condition = False
return sol_str
# test = base10_to_base94_fct(94**2-1)
# print(f'TEST result: {test}')
def comb_fct(word_length: int) -> None:
max_iter = 94**word_length
cnt = 1
while cnt < max_iter:
str_tmp = base10_to_base94_fct(cnt)
cnt = 1
print(f'{cnt}: Current word check:{str_tmp}')
# Test
comb_fct(3)
版本 2：
如果您對獲取表單的所有單詞感興趣，例如長度為 2，“！R”（在我們的基礎中，“！”等于零。
# Get all ascii relevant character in a list
asciiList = []
for c in (chr(i) for i in range(33, 127)):
asciiList.append(c)
print(f'The word should contain only the character in the following ascii List: \n{asciiList} \nlist length: {len(asciiList)}')
def base10_to_base94_fct(int_to_convert: int, str_length: int) -> bytearray:
sol_str = bytearray(b'\x21') * str_length
digit_nbr = str_length-1
loop_condition = True
while loop_condition is True:
quo = int_to_convert // 94
mod = int_to_convert % 94
sol_str[digit_nbr] = 33 mod
digit_nbr -= 1
int_to_convert = quo
if digit_nbr == -1:
loop_condition = False
return sol_str
def comb_fct(max_word_length: int) -> None:
max_iter_abs = (94/93) * (94**max_word_length-1) # sum of a geometric series: 94 94^2 94^3 94^4 ... 94^N
max_iter_rel = 94
word_length = 1
cnt_rel = 0 # rel = relative
cnt_abs = 0 # abs = absolute
while cnt_rel < max_iter_rel**word_length and cnt_abs < max_iter_abs:
str_tmp = base10_to_base94_fct(cnt_rel, word_length)
print(f'{cnt_abs}:Current word test:{str_tmp}.')
print(f'cnt_rel = {cnt_rel} and cnt_abs={cnt_abs}')
if str_tmp == bytearray(b'\x7e') * word_length:
word_length = 1
cnt_rel = 0
continue
cnt_rel = 1
cnt_abs = 1
comb_fct(2) # Test
基本轉換示例：
https
://www.rapidtables.com/convert/number/decimal-to-hex.html
運算子“//”是商運算子，運算子“%”是模運算子。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/496377.html
下一篇：多針遞回搜索陣列-PHP