按权重顺序从加权集中生成长度 L 的前 N 个组合
Generate first N combinations of length L from weighted set in order of weight
我有一组带有权重的字母，它给出了它们出现在字符串中的概率：
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。同一个词的所有排列都有相同的概率，所以我们只需要担心组合。
我想按概率顺序生成长度为 L 的第一个唯一 N 字符串（例如这里有 4 个字母，长度为 4，应该是 aaaa , aaac, aacc, aaab, accc, aabc, cccc, 等）。
假设用它们的概率生成所有组合并按重量排序的蛮力方法在这里是不可能的。该算法（如果存在）必须能够适用于任何集合大小和任何长度的字符串（例如，所有 256 字节的加权概率，1024 长度的字符串，生成第一个万亿。）
下面是一些使用堆的枚举代码。实现原理与user3386109在他们的评论中提出的略有不同。
按概率递减对符号进行排序。在 S 个符号的 length-L 组合与长度为 S + L − 1 且带有 L − 1 个零的二进制字符串之间存在建设性的 one-to-one 对应关系（用 L − 1 个分隔符计算出每个一元符号）。我们可以bit-at-a-time枚举后者的可能性。
使我们不必枚举每个组合的部分是，对于每个二进制前缀，可以通过重复仍然可用的最可能的字母来找到最可能的单词。通过将前缀存储在堆中，我们可以只打开出现在前 N 个的前缀。
请注意，这使用的内存与枚举组合的数量成正比。这可能仍然太多，在这种情况下，您可能需要迭代加深 depth-first 搜索之类的东西。
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
此答案提供了@user3386109 评论的实现：
I think the solution is a priority queue. The initial input to the queue is a string with the highest probability letter (aaaa). After reading a string from the queue, replace a letter with the next lower probability letter, and add that new string to the queue. So after reading aaaa, write aaac. After reading aaac, write aacc (changing an a to c) and aaab (changing a c to a b).
我写了一个生成器函数，具体步骤如下：
- 定义一个辅助函数：
prio(word)其中returns一个词的优先级（为负数，因为python堆是min-heaps）；
- 定义辅助字典：
next_letter.get(letter)是letter之后的下一个higher-priority字母，如果有的话；
- 用第一个词
aaaa 及其相应的优先级初始化一个 heapq 队列；
- 从队列中弹出单词时，通过将当前单词与前一个单词进行比较来避免可能的重复；
- 从队列中弹出一个单词后，如果不是重复的，则
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']
首先请原谅我指出你的概率之和不等于 1 这让我立刻觉得有些不对劲。
我想分享我的版本（感谢 Stef、David 和 user3386109），在 space 和 O(N*max(L,log) 中更容易证明是 O(NL) (N))) 及时。因为你需要O(NL)才能store/print出结果，并且为prio-queue加上一个log(N)，可以看出很难进一步改进。我没有看到这里的人在 complexity-wise 上证明足够有效。 P.S，使其成为生成器无济于事，因为 space 主要是由堆本身引起的。 P.S.2 对于大L，N的大小可以是天文数字。
复杂度分析：堆从1个元素开始，每次弹出，即top-N中的一个，推回2个元素。因此，总共space为O(N 2项目大小)=O(NL)。时间成本为 N*max(L,log(N))，因为 push/pop 每个步骤的成本为 log(N)，而内部循环中的许多步骤成本为 O(L)。
您可以看到它打印出与 Stef 相同的 35 个结果。现在这个算法的核心部分是如何选择每次弹出后要推送的 2 个元素。首先考虑相反的问题，如何找到每个child的parent 所以（1）所有可能的组合形成一个偏序（最大元素是'aaaa'，并且我们不需要Zorn 的引理在这里），（2）我们不会错过任何大于 child 但小于 parent 的东西（对于 2 个字母具有相同概率的陈述不是完全正确的，但实际上我发现没关系），并且（3）没有重复，所以我们不必管理缓存访问的字符串。我选择 parent 的方法总是降低字符串前面的字母，直到达到 'a'。例如，'cbbz' 的 parent 将是 'abbz' 而不是 'ccbz'。相反，我们找到给定 parent 的 children，很高兴看到在这种情况下我们最多有 2 children：提高第一个非 'a' 字母直到它等于下一个字母，（'acbb'=>'abbb'，而 'accb' 在这个方向上没有 child ）或提高最后一个 'a' （ 'acbb'=>'ccbb', 'accb'=>'cccb')
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])
我有一组带有权重的字母，它给出了它们出现在字符串中的概率：
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。同一个词的所有排列都有相同的概率，所以我们只需要担心组合。
我想按概率顺序生成长度为 L 的第一个唯一 N 字符串（例如这里有 4 个字母，长度为 4，应该是 aaaa , aaac, aacc, aaab, accc, aabc, cccc, 等）。
假设用它们的概率生成所有组合并按重量排序的蛮力方法在这里是不可能的。该算法（如果存在）必须能够适用于任何集合大小和任何长度的字符串（例如，所有 256 字节的加权概率，1024 长度的字符串，生成第一个万亿。）
下面是一些使用堆的枚举代码。实现原理与user3386109在他们的评论中提出的略有不同。
按概率递减对符号进行排序。在 S 个符号的 length-L 组合与长度为 S + L − 1 且带有 L − 1 个零的二进制字符串之间存在建设性的 one-to-one 对应关系（用 L − 1 个分隔符计算出每个一元符号）。我们可以bit-at-a-time枚举后者的可能性。
使我们不必枚举每个组合的部分是，对于每个二进制前缀，可以通过重复仍然可用的最可能的字母来找到最可能的单词。通过将前缀存储在堆中，我们可以只打开出现在前 N 个的前缀。
请注意，这使用的内存与枚举组合的数量成正比。这可能仍然太多，在这种情况下，您可能需要迭代加深 depth-first 搜索之类的东西。
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
此答案提供了@user3386109 评论的实现：
I think the solution is a priority queue. The initial input to the queue is a string with the highest probability letter (
aaaa). After reading a string from the queue, replace a letter with the next lower probability letter, and add that new string to the queue. So after readingaaaa, writeaaac. After readingaaac, writeaacc(changing anatoc) andaaab(changing acto ab).
我写了一个生成器函数，具体步骤如下：
- 定义一个辅助函数：
prio(word)其中returns一个词的优先级（为负数，因为python堆是min-heaps）； - 定义辅助字典：
next_letter.get(letter)是letter之后的下一个higher-priority字母，如果有的话； - 用第一个词
aaaa及其相应的优先级初始化一个heapq队列； - 从队列中弹出单词时，通过将当前单词与前一个单词进行比较来避免可能的重复；
- 从队列中弹出一个单词后，如果不是重复的，则
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']
首先请原谅我指出你的概率之和不等于 1 这让我立刻觉得有些不对劲。
我想分享我的版本（感谢 Stef、David 和 user3386109），在 space 和 O(N*max(L,log) 中更容易证明是 O(NL) (N))) 及时。因为你需要O(NL)才能store/print出结果，并且为prio-queue加上一个log(N)，可以看出很难进一步改进。我没有看到这里的人在 complexity-wise 上证明足够有效。 P.S，使其成为生成器无济于事，因为 space 主要是由堆本身引起的。 P.S.2 对于大L，N的大小可以是天文数字。
复杂度分析：堆从1个元素开始，每次弹出，即top-N中的一个，推回2个元素。因此，总共space为O(N 2项目大小)=O(NL)。时间成本为 N*max(L,log(N))，因为 push/pop 每个步骤的成本为 log(N)，而内部循环中的许多步骤成本为 O(L)。
您可以看到它打印出与 Stef 相同的 35 个结果。现在这个算法的核心部分是如何选择每次弹出后要推送的 2 个元素。首先考虑相反的问题，如何找到每个child的parent 所以（1）所有可能的组合形成一个偏序（最大元素是'aaaa'，并且我们不需要Zorn 的引理在这里），（2）我们不会错过任何大于 child 但小于 parent 的东西（对于 2 个字母具有相同概率的陈述不是完全正确的，但实际上我发现没关系），并且（3）没有重复，所以我们不必管理缓存访问的字符串。我选择 parent 的方法总是降低字符串前面的字母，直到达到 'a'。例如，'cbbz' 的 parent 将是 'abbz' 而不是 'ccbz'。相反，我们找到给定 parent 的 children，很高兴看到在这种情况下我们最多有 2 children：提高第一个非 'a' 字母直到它等于下一个字母，（'acbb'=>'abbb'，而 'accb' 在这个方向上没有 child ）或提高最后一个 'a' （ 'acbb'=>'ccbb', 'accb'=>'cccb')
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])