python - 有效地“完成”一组算法

Question

我有一个困扰我的小玩具问题。我认为它等同于任何数量的更严重的等价问题。不，这不是一个家庭作业或面试问题......虽然如果我觉得我知道一个可证明的最佳解决方案，我可能会在某个时候用它来采访人们。

我学会了supervocalic这个词（一个形容词，描述一个包含五个元音——A、E、I、O 和 U——中的每一个的单词或短语，恰好一次）。例如“问号”、“灵巧”，当然还有“超级声音”。

我写了一个小 Python 程序来识别超发音词。这很容易，它的核心是：

matches = {}
for w in words:
    pat = tuple(w.count(v) for v in vowels)
    if pat in matches:
        matches[pat].add(w)
    else:
        matches[pat] = {w}

words只是来自我拥有的一个大型单词表（SOWPODS Scrabble 字典，大约有 270k 个单词。我可以简单地用matches[(1,1,1,1,1)]... 来识别超语音单词，即每个元音中恰好有一个单词是什么。FWIWvowels在技术上是可配置的，所以我的小脚本可以对任何字符子集（和任何单词表）做同样的事情。

我的问题是我想找到所有超语音的ngram。单词是 1 克。什么 2-grams、3-grams 等等也可以构成超语音短语。原来我有175个字没有AEIOU；因此从技术上讲，这些幂集的每个元素都可以附加到不包含它们的每个 ngram 上。好多啊。

但是忽略每个“填充”超音节的那些 2^175 额外变体，我如何组合计数元组。就元音计数而言，有很多等价词，所以当然有很多组合，例如：

pat: (1, 0, 1, 0, 0); numwords: 5499
pat: (0, 1, 0, 1, 1); numwords: 2703

因此，从第一个列出的组中抽取任何一个，从第二个列出的组中抽取任何其他人都符合条件。那是 14,863,797 2 克。实际上，因为任何一个订单都可以，所以数量是原来的两倍。

让我们也假设我已经抛弃了具有不止一个元素的每个模式，这些词不能包含在任何超元音短语中，因为它们本身就太“元音丰富”了。

我可以通过眼球看到它们是互补的模式(1, 0, 1, 0, 0)，(0, 1, 0, 1, 1)它们将一起“填充”元音空间（或问题的一般版本中的任何元素空间）。对于任意长度的任意元组，我如何找到所有 N 大小的元组集合，这些集合将组合为“填充元组”（但不是过度填充的元组）？

从本质上讲，尽管有引导，但我的问题是找到这些互补的 N 大小的元组集合......以最有效的方式可能用于任意元组长度，而不仅仅是长度 5。即使我更喜欢 Python 和我的短代码片段就是，这个问题应该适用于几乎任何编程语言。

标签： pythonalgorithmperformancesetbig-o