查找所有可能的N长度字谜-快速替代 [英] Find all the possible N-length anagrams - fast alternatives

问题描述

我被赋予了一个字母序列，并且必须产生给定序列的所有N长度字谜，其中N是序列的长度.

I am given a sequence of letters and have to produce all the N-length anagrams of the sequence given, where N is the length of the sequence.

我在python中遵循一种幼稚的方法，在其中我采用了所有排列以实现该目的.我发现了一些类似的线程，例如该线程，但我更喜欢面向数学的方法在Python中.那么，什么是替代置换性能更好的替代品呢?我在下面的尝试中有什么特别错误的地方吗?

I am following a kinda naive approach in python, where I am taking all the permutations in order to achieve that. I have found some similar threads like this one but I would prefer a math-oriented approach in Python. So what would be a more performant alternative to permutations? Is there anything particularly wrong in my attempt below?

from itertools import permutations
def find_all_anagrams(word):

pp = permutations(word)
perm_set = set()
for i in pp:
    perm_set.add(i)
ll = [list(i) for i in perm_set]
ll.sort()
print(ll)

推荐答案

如果有很多重复的字母，关键是每个字母仅产生一次，而不是产生所有可能的排列并消除重复.

If there are lots of repeated letters, the key will be to produce each anagram only once instead of producing all possible permutations and eliminating duplicates.

这里是一种可能的算法，它只产生一次字谜一次:

Here's one possible algorithm which only produces each anagram once:

from collections import Counter

def perm(unplaced, prefix):
  if unplaced:
    for element in unplaced:
      yield from perm(unplaced - Counter(element), prefix + element)
  else:
    yield prefix

def permutations(iterable):
  yield from perm(Counter(iterable), "")

与产生所有排列的经典递归实际上并没有太大区别；唯一的区别是它使用了 collections.Counter (一个多集)来保存尚未放置的元素，而不仅仅是使用列表.

That's actually not much different from the classic recursion to produce all permutations; the only difference is that it uses a collections.Counter (a multiset) to hold the as-yet-unplaced elements instead of just using a list.

在迭代过程中产生的 Counter 对象的数量肯定是过多的，几乎可以肯定有一种更快的书写方式；我选择此版本是因为其简单性和(希望)其清晰性

The number of Counter objects produced in the course of the iteration is certainly excessive, and there is almost certainly a faster way of writing that; I chose this version for its simplicity and (hopefully) its clarity

这篇关于查找所有可能的N长度字谜-快速替代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！