python - 在python中用逗号运算符分隔的行中查找字谜单词

Question

>>> line = "cat,ant,ate,abc,tan,act,tea"
>>> words = line.split(",")
>>> words
['cat', 'ant', 'ate', 'abc', 'tan', 'act', 'tea']
>>> sorted_words = map(tuple, [sorted(eachword) for eachword in words])
>>> sorted_words
[('a', 'c', 't'), ('a', 'n', 't'), ('a', 'e', 't'), ('a', 'b', 'c'), ('a', 'n', 't'), ('a', 'c', 't'), ('a', 'e', 't')]
>>> repeated_words = set(sorted_words)
>>> repeated_words
set([('a', 'b', 'c'), ('a', 'e', 't'), ('a', 'c', 't'), ('a', 'n', 't')])
>>> for repeated_word in repeated_words:
    for index in [i for i, x in enumerate(sorted_words) if sorted_words.count(x) > 1 and x == repeated_word]:
        print words[index],
    print '\t'



ate tea     
cat act     
ant tan

能够在一行中得到字谜，但想知道是否有更好的方法可以更简单地解决上述问题。请帮助我计算上述方法的复杂性。

Answer 1

这里最大的效率问题是 if sorted_words.count(x) > 1你对每个人所做的。

让我们来看看这些部分。假设我们有 N 个元素，K 个唯一元素，平均单词长度为 M。

• 对列表中的每个元素进行排序，并将结果放入另一个列表中。那是 O(MlogM)每个元素的时间，或 O(NMlogM)总计。
• 用新列表做一个集合，即O(N) .
• 对于集合中的每个单词，对于列表中的每个单词，计算列表单词在列表中出现的次数。这是大人物。计算某项在列表中出现的次数需要 O(N)时间，你做到了KN次，所以这是 O(N^2 * K) .
• 对于集合中的每个单词，如果 count > 1 出现，则迭代列表以找到所有匹配值.那是 O(NK)时间。

你可以修复 O(N^2 * K)部分只是将计数从列表理解中移除。让我们假设你这样做了，但没有解释具体是怎么做的(这很容易)。现在你的时间是O(NMlogM + N + NK) .假设 M << K , 那是 O(NK) .

---

要解决此问题，您需要创建一个从排序词到原始词的映射，以便您可以在恒定时间内查找原始词。

例如:

>>> repeated_words = {}
>>> for word in words:
...     sorted_word = tuple(sorted(word))
...     repeated_words.setdefault(sorted_word, set()).add(word)
>>> repeated_words
{('a', 'b', 'c'): {'abc'},
 ('a', 'c', 't'): {'act', 'cat'},
 ('a', 'e', 't'): {'ate', 'tea'},
 ('a', 'n', 't'): {'ant', 'tan'}}
>>> for repeated_word, words in repeated_words.viewitems():
...     if len(words) > 1:
...         print(' '.join(words))
tea ate
act cat
ant tan

现在，我们的前两个步骤是 O(NMlogM + N) , 但我们的第三步是 O(K)而不是 O(KN) ，因为我们只是对每个集合词进行一次恒定时间集合查找，而不是对每个集合词进行一次线性列表遍历。

所以我们的总时间是O(NMlogM) .

(如果每个集合中字谜的顺序很重要，或者如果可能存在实际重复的单词，您可以将每个排序的单词映射到一个列表而不是一组原始单词。这不会真正影响这里的性能，因为我们对该列表/集合所做的唯一事情就是追加/添加和迭代；我只是使用了一个集合，因为它在概念上看起来顺序是无关紧要的，不应该有任何重复。)

---

但我们可以做得更好。考虑到M << K，这可能无关紧要，但是……

为什么我们需要对单词进行排序？因为如果两个单词相同，那么它们排序后的字母也相同。但是，如果两个单词相同，则它们的字母组也相同，只要没有任何重复的字母——在您的示例中没有。 (即使有有，您也可以使用“多重集”来处理它，例如 Counter ，但不可变且可散列……虽然这样比较就不再是恒定的时间了，它们取决于平均值重复字母的数量……让我们忽略这种复杂性，因为它与您的示例无关，但如果需要我们可以解决。)

>>> repeated_words = {}
>>> for word in words:
...     letter_set = frozenset(word)
...     repeated_words.setdefault(letter_set, set()).add(word)
>>> repeated_words
{frozenset({'a', 'b', 'c'}): {'abc'},
 frozenset({'a', 'e', 't'}): {'ate', 'tea'},
 frozenset({'a', 'n', 't'}): {'ant', 'tan'},
 frozenset({'a', 'c', 't'}): {'act', 'cat'}}
>>> for repeated_word, words in repeated_words.viewitems():
...     if len(words) > 1:
...         print(' '.join(words))
tea ate
ant tan
act cat

现在，我们的总时间仅为 O(NM)而不是 O(NMlogM) .

同样，最后的改进可能不值得做(特别是如果您需要多集解决方案，因为我们花时间弄清楚如何表达 Counter.__eq__ 的复杂性，以及构建和解释 FrozenCounter，是考虑到 M << K，可能比我们节省运行程序的时间还要多:) .