我得到了一个字母序列,我必须生成给定序列的所有 N 长度的变位词,其中 N 是序列的长度。
我在 python 中采用了一种有点幼稚的方法,我正在采用所有排列来实现这一点。我发现了一些类似的话题,例如 this one但我更喜欢 Python 中面向数学的方法。那么什么是比排列更高效的替代方案呢?我在下面的尝试中有什么特别错误的地方吗?
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)
最佳答案
如果有很多重复的字母,关键是只生成每个变位词一次,而不是生成所有可能的排列并消除重复项。
这是一种可能的算法,它只生成每个变位词一次:
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 (多重集)来保存尚未放置的元素,而不仅仅是使用列表。
在迭代过程中产生的 Counter
对象的数量肯定过多,而且几乎肯定有一种更快的写法;我选择这个版本是因为它的简单性和(希望)它的清晰度
关于python - 找到所有可能的 N 长度字谜 - 快速替代,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44852201/