給出一個 baseb和一個 length n，我想找到 baseb中的所有整數，前導零達到 length n，滿足：
對于數字 i 和 j，如果 i < j 則 i 的計數 >= j 的計數。
例如，底數 3，長度 4：
0000, 0001, 0010, 0011, 0012, 0021, 0100,
0101, 0102, 0110, 0120, 0201, 0210 1000,
1001, 1002, 1010, 1020, 1100, 1200, 2001,
2010, 2100
我目前的方法是遞增以 10 為底的范圍內的所有整數，轉換為以 b 為底，計算數字，如果數字計數不符合我們的標準，則拒絕。這很慢。
我認為我使用的語言無關緊要，但如果重要的話，那就是 Rust。
uj5u.com熱心網友回復：
這個問題可以用動態規劃來解決。這是一種方法（使用 Python）：
from functools import lru_cache
from collections import Counter
from itertools import product
def naive(base, length):
result = 0
for tup in product(range(base), repeat=length):
ctr = Counter(tup)
is_valid = all(ctr[i] >= ctr[i 1] for i in range(base))
if is_valid:
result = 1
return result
@lru_cache(None)
def binom(n, k):
# compute binomial coefficient
if n == 0:
if k == 0:
return 1
else:
return 0
return binom(n - 1, k) binom(n - 1, k - 1)
def count_seq(base, length):
@lru_cache(None)
def count_helper(base, length, max_repeats):
if base < 0 or length < 0:
return 0
elif length == 0:
return 1
return sum(binom(length, k) * count_helper(base - 1, length - k, k)
for k in range(max_repeats 1))
return count_helper(base, length, length)
assert all(count_seq(base, length) == naive(base, length)
for base in range(7) for length in range(7))
print(count_seq(100, 60))
#21047749425803338154212116084613212619618570995864645505458031212645031666717071397
關鍵功能是count_helper(base, length, max_repeats)計算最常見數字不重復多次的有效序列數max_repeats。忽略基本情況，此函式滿足遞回關系：
count_helper(base, length, max_repeats) = sum(
binom(length, k) * count_helper(base - 1, length - k, k)
for k in range(max_repeats 1))
此時，我們正在決定將多少個數字副本base插入序列中。我們可以選擇k介于兩者之間0的任何數字max_repeats。對于給定的 值k，有length choose k多種方法可以插入我們要添加的數字。每個選擇都會k導致對子問題的遞回呼叫，其中基數減少1，長度減少k并max_repeats設定為k。
uj5u.com熱心網友回復：
當 base = 3 和 length = 4 時，答案是
['0000'，'0001'，'0010'，'0011'，'0012'，'0021'，'0100'，'0101'，'0102'，'0110'，'0120'，'0201'，' 0210'、'1000'、'1001'、'1002'、'1010'、'1020'、'1100'、'1111'、'1112'、'1121'、'1122'、'1200'、'1211' , '1212', '1221', '2001', '2010', '2100', '2111', '2112', '2121', '2211', '2222']
我們可以觀察到答案中的所有數字都是 ['0000', '0001', '0011', '0012', '1111', '1112', '1122', '2222'] 的排列。讓我們打電話給他們unique_numbers。
因此，我們的解決方案簡單易行。生成所有unique_numbers并將它們的排列添加到result.
from itertools import permutations
base = 3
length = 4
unique_numbers = []
def getUniqueNumbers(curr_digit, curr_count, max_count, curr_num):
#Add the curr_num to unique_numbers
if len(curr_num) == length:
unique_numbers.append(curr_num)
return
#Try to include the curr_digit again
if curr_count 1 <= max_count:
getUniqueNumbers(curr_digit, curr_count 1, max_count, curr_num str(curr_digit))
#Try to include the next digit
if curr_digit 1 < base:
getUniqueNumbers(curr_digit 1, 1, curr_count, curr_num str(curr_digit 1))
#Try generating unique numbers starting with every digit
for i in range(base):
getUniqueNumbers(i, 0, length, "")
result = set()
for num in unique_numbers:
permList = permutations(num)
for perm in list(permList):
result.add(''.join(perm))
print(result)
uj5u.com熱心網友回復：
這個問題相當于將值的整數磁區生成n部分b，然后使用每個磁區元素作為數字計數并應用排列（最后階段類似于 Shridhar R Kulkarni 方法，但使用了另一個組合物件）
For n=7and b=4some intermediate partition of 7into 4parts[3, 2, 2, 0]表示數字組合[0, 0, 0, 1, 1, 2, 2]，然后我們按字典順序排列最后一個。partitions函式提供非遞增的零件順序，因此if i < j then the count of i's is >= the count of j's.滿足條件。
可以使用的Ideone 代碼。
def next_permutation(arr):
#https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
i = len(arr) - 1
while i > 0 and arr[i - 1] >= arr[i]:
i -= 1
if i <= 0:
return False
j = len(arr) - 1
while arr[j] <= arr[i - 1]:
j -= 1
arr[i - 1], arr[j] = arr[j], arr[i - 1]
arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
return True
def partitions(Sum, K, lst, Minn = 0):
if K == 0:
if Sum == 0:
#print(lst) [3, 1, 0] denotes three zeros and one 1
arr = []
for i in range(len(lst)):
if lst[i]:
arr.extend([i]*lst[i])
#transform [3, 1, 0] to [0,0,0,1]
print(arr)
while next_permutation(arr):
print(arr)
return
for i in range(Minn, min(Sum 1, Sum 1)):
partitions(Sum - i, K - 1, [i] lst, i)
b = 3
n = 4
partitions(n, b, [])
結果
[0, 0, 0, 0] [0, 0, 0, 1] [0, 0, 1, 0] [0, 1, 0, 0]
[1, 0, 0, 0] [0, 0, 1, 1] [0, 1, 0, 1] [0, 1, 1, 0]
[1, 0, 0, 1] [1, 0, 1, 0] [1, 1, 0, 0] [0, 0, 1, 2]
[0, 0, 2, 1] [0, 1, 0, 2] [0, 1, 2, 0] [0, 2, 0, 1]
[0, 2, 1, 0] [1, 0, 0, 2] [1, 0, 2, 0] [1, 2, 0, 0]
[2, 0, 0, 1] [2, 0, 1, 0] [2, 1, 0, 0]
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415939.html
標籤：
上一篇：如何解決中文WhispersPython問題'AttributeError:'Graph'objecthasnoattribute'node'