我有一組帶權重的字母，它們給出了它們出現在字串中的概率：
a - 0.7
b - 0.1
c - 0.3
...
z - 0.01
因此，這個詞aaaa的概率為0.7*0.7*0.7*0.7 = 0.24。這個詞aaac會有概率0.7*0.7*0.7*0.3 = 0.10。同一個詞的所有排列都有相同的概率，所以我們只需要擔心組合。
我想按概率順序生成第一個N長度唯一的字串L（例如，這里有 4 個字母和長度 4，應該是aaaa, aaac, aacc, aaab, accc, aabc,cccc等）。
假設在這里不可能使用暴力方法生成所有組合及其概率并按重量排序。如果存在該演算法，它必須能夠適用于任何設定的大小和任何長度的字串（例如，所有 256 個具有加權概率的位元組，1024 長度的字串，生成第一個萬億。）
uj5u.com熱心網友回復：
下面是一些使用堆的列舉代碼。實作原理與 user3386109 在他們的評論中提出的略有不同。
通過降低概率對符號進行排序。S 符號的長度為 L 的組合與長度為 S L - 1 和 L - 1 個零的二進制字串之間存在建設性的一對一對應關系（用 L - 1 個分隔符計算一元中的每個符號）。我們可以逐位列舉后者的可能性。
使我們不必列舉每個組合的部分是，對于每個二進制前綴，可以通過重復仍然可用的最可能的字母來找到最可能的單詞。通過將前綴存盤在堆中，我們可以只打開出現在前 N 個中的前綴。
請注意，這使用與列舉組合數量成比例的記憶體。這可能仍然太多，在這種情況下，您可能需要諸如迭代深化深度優先搜索之類的東西。
symbol_probability_dict = {"a": 0.7, "b": 0.1, "c": 0.3, "z": 0.01}
L = 4
import heapq
import math
loss_symbol_pairs = [(-math.log(p), c) for (c, p) in symbol_probability_dict.items()]
loss_symbol_pairs.sort()
heap = [(0, 0, "")]
while heap:
min_loss, i, s = heapq.heappop(heap)
if len(s) < L:
heapq.heappush(heap, (min_loss, i, s loss_symbol_pairs[i][1]))
if i 1 < len(loss_symbol_pairs):
heapq.heappush(
heap,
(
min_loss
(L - len(s))
* (loss_symbol_pairs[i 1][0] - loss_symbol_pairs[i][0]),
i 1,
s,
),
)
else:
print(s)
輸出：
aaaa
aaac
aacc
aaab
accc
aacb
cccc
accb
aabb
aaaz
cccb
acbb
aacz
ccbb
abbb
accz
aabz
cbbb
cccz
acbz
bbbb
ccbz
abbz
aazz
cbbz
aczz
bbbz
cczz
abzz
cbzz
bbzz
azzz
czzz
bzzz
zzzz
uj5u.com熱心網友回復：
這個答案提供了@user3386109 評論的實作：
我認為解決方案是優先佇列。佇列的初始輸入是具有最高概率字母 (
aaaa) 的字串。從佇列中讀取一個字串后，將一個字母替換為下一個概率較低的字母，并將該新字串添加到佇列中。所以讀完aaaa之后再寫aaac。讀完后aaac，寫aacc（把 ana改成c）和aaab（把 ac改成 ab）。
我按照以下確切步驟撰寫了一個生成器函式：
- 定義一個輔助函式：
prio(word)它回傳一個單詞的優先級（作為負數，因為 python 堆是最小堆）； - 定義一個輔助字典：
next_letter.get(letter)是 之后的下一個更高優先級的字母letter，如果有的話； heapq用第一個單詞aaaa及其相應的優先級初始化一個佇列；- 從佇列中彈出單詞時，通過將當前單詞與前一個單詞進行比較來避免可能的重復；
- 從佇列中彈出一個詞后，如果不是重復詞，則為
yield該詞，并將一個字母替換為下一個概率字母得到的詞推送；
因為它是一個生成器函式，所以它是惰性的：你可以在N不計算所有單詞的情況下獲得第一個單詞。但是，仍然會計算一些額外的單詞，因為優先級佇列的整個想法是我們事先不知道確切的順序。
import heapq
from math import prod
from itertools import pairwise
def gen_combs(weights, r = 4):
next_letter = dict(pairwise(sorted(weights, key=weights.get, reverse=True)))
def prio(word, weights=weights):
return -prod(map(weights.get, word))
first_word = max(weights, key=weights.get) * r
queue = [(prio(first_word), first_word)]
prev_word = None
while queue:
w, word = heapq.heappop(queue)
if word != prev_word:
yield word
prev_word = word
seen_letters = set()
for i, letter in enumerate(word):
if letter not in seen_letters:
new_letter = next_letter.get(letter)
if new_letter:
new_word = ''.join((word[:i], new_letter, word[i 1:]))
heapq.heappush(queue, (prio(new_word), new_word))
seen_letters.add(letter)
# TESTING
weights = {'a': 0.7, 'b': 0.1, 'c': 0.3, 'z': 0.01}
# print all words
print(list(gen_combs(weights)))
# ['aaaa', 'caaa', 'ccaa', 'baaa', 'ccca', 'bcaa', 'cccc',
# 'bcca', 'bbaa', 'zaaa', 'bccc', 'bbca', 'zcaa', 'bbcc',
# 'bbba', 'zcca', 'zbaa', 'bbbc', 'zccc', 'zbca', 'bbbb',
# 'zbcc', 'zbba', 'zzaa', 'zbbc', 'zzca', 'zbbb', 'zzcc',
# 'zzba', 'zzbc', 'zzbb', 'zzza', 'zzzc', 'zzzb', 'zzzz']
n = 10
# print first n words, one per line
for _,word in zip(range(n), gen_combs(weights)):
print(word)
# print first n words
from itertools import islice
print(list(islice(gen_combs(weights), n)))
# ['aaaa', 'caaa', 'ccaa', 'baaa', 'ccca', 'bcaa', 'cccc', 'bcca', 'bbaa', 'zaaa']
uj5u.com熱心網友回復：
首先請原諒我指出您的概率總和不等于 1，這立即讓我覺得有些不對勁。
我想分享我的版本（感謝 Stef、David 和 user3386109），它更容易證明在空間上是 O(NL)，在時間上是 O(N*max(L,log(N)))。因為你需要 O(NL) 來存盤/列印結果，并為 prio-queue 添加一個 log(N)，你可以看到很難進一步改進。我沒有看到這里的人在復雜性方面證明足夠有效。PS，使其成為生成器無濟于事，因為空間主要是由堆本身引起的。PS2對于大L，N的大小可以是天文數字。
復雜度分析：堆從 1 個元素開始，每個 pop，即 top-N 之一，最多推回 2 個元素。因此，總空間為 O(N 2 item size)=O(NL)。時間成本是 N*max(L,log(N))，因為每個 push/pop 都花費 log(N)，而內部回圈中的許多步驟花費 O(L)。
您可以看到它列印出與 Stef 相同的 35 個結果。現在這個演算法的核心部分是如何在每次彈出后選擇要推送的 2 個元素。首先考慮相反的問題，如何找到每個孩子的父母，所以（1）所有可能的組合形成偏序（最大元素是'aaaa'，不，我們不需要 Zorn 引理），（2）我們贏了'不要錯過任何大于孩子但小于父母的東西（對于共享相同概率的 2 個字母來說，這不是一個完全正確的說法，但實際上我發現這并不重要），并且（3）沒有重復，所以我們沒有管理快取訪問的字串。我選擇父母的方式總是降低字串前面的字母，直到它達到'a'。例如，'cbbz' 的父級將是 'abbz' 而不是 'ccbz'。反過來，
import heapq, math
letters=[[-math.log(x[1]),x[0]] for x in zip('abcz',[0.7,0.1,0.3,0.01])]
N=35 #something big to force full print in testing. Here 35 is calculated by DP or Pascal triangle
L=4
letters.sort()
letters=[[i,x[0],x[1]] for i,x in enumerate(letters)]
heap=[[letters[0][1]*L,[0]*L,L-1]]
while heap and N>0:
N-=1
p,nextLargest,childPtr=heapq.heappop(heap)
print(''.join([letters[x][2] for x in nextLargest]))
if childPtr<L-1 and nextLargest[childPtr 1]<len(letters)-1:
child=list(nextLargest)
child[childPtr 1] =1
if childPtr 2==L or child[childPtr 1]<=child[childPtr 2]:
prob=sum([letters[x][1] for x in child]) #this can be improved by using a delta, but won't change overall complexity
heapq.heappush(heap,[prob,child,childPtr])
if childPtr>=0:
child=list(nextLargest)
child[childPtr] =1
prob=sum([letters[x][1] for x in child])
heapq.heappush(heap,[prob,child,childPtr-1])
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471208.html
上一篇：難以簡化條件