从加权集中按权重顺序生成长度 L 的前 N ​​个组合

我有一组带有权重的字母，这给出了它们出现在字符串中的概率：

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, etc).

假设生成所有组合及其概率并按权重排序的强力方法在这里是不可能的。该算法（如果存在）必须能够适用于任何集合大小和任何长度的字符串（例如，具有加权概率的所有 256 个字节、1024 长度的字符串，生成第一个万亿。）

下面是一些使用堆的枚举代码。实现原理与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)

Output:

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