查找所有可能的N长度字符 - 快速替代

Question

我给出了一个字母序列并且必须产生给定序列的所有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) 

Answer 1

也许我失去了一些东西，但你为什么不只是这样做：

from itertools import permutations 

def find_all_anagrams(word): 
    return sorted(set(permutations(word))) 

Answer 2

这是与许多类似的字符长的话很慢。与理论上的最大性能相比较慢。例如，permutations("mississippi")将产生比必要更长的列表。这将有39916800的长度，但却集合的大小为34650.

>>> len(list(permutations("mississippi"))) 
39916800 
>>> len(set(permutations("mississippi"))) 
34650 

因此，与您的方法大缺陷就是你生成所有字谜，然后删除重复的。使用只生成唯一字母的方法。

编辑：

下面是一些工作，但非常难看，并可能bug的代码。当你阅读这篇文章时，我会更好。它确实给密西西比州34650，所以我认为没有任何重大错误。再次警告。丑陋！

# Returns a dictionary with letter count 
# get_letter_list("mississippi") returns 
# {'i':4, 'm':1, 'p': 2, 's':4} 
def get_letter_list(word): 
    w = sorted(word) 
    c = 0 
    dd = {} 
    dd[w[0]]=1 
    for l in range(1,len(w)): 
     if w[l]==w[l-1]: 
      d[c]=d[c]+1 
      dd[w[l]]=dd[w[l]]+1 
     else: 
      c=c+1 
      d.append(1) 
      dd[w[l]]=1 
    return dd 

def sum_dict(d): 
    s=0 
    for x in d: 
     s=s+d[x] 
    return s 

# Recursively create the anagrams. It takes a letter list 
# from the above function as an argument. 
def create_anagrams(dd): 
    if sum_dict(dd)==1: # If there's only one letter left 
     for l in dd: 
      return l # Ugly hack, because I'm not used to dics 
    a = [] 
    for l in dd: 
     if dd[l] != 0: 
      newdd=dict(dd) 
      newdd[l]=newdd[l]-1 
      if newdd[l]==0: 
       newdd.pop(l) 
      newl=create(newdd) 
     for x in newl: 
      a.append(str(l)+str(x)) 
    return a 

>>> print (len(create_anagrams(get_letter_list("mississippi")))) 
34650 

它的工作原理是这样的：对于每一个独特的字母l，创造一切的独特排列有字母L少了一个次数，然后追加L到所有这些排列。

对于“密西西比州”来说，这比设置（排列（单词））快得多，而且它远没有最佳书写。例如，字典非常慢，在这段代码中可能有很多事情要改进，但是它表明算法本身比你的方法快得多。

Answer 3

你可以简化为：

from itertools import permutations 

def find_all_anagrams(word): 
    word = set(''.join(sorted(word))) 
    return list(permutations(word)) 

在DOC为permutations代码的相关详细，似乎已经过优化。

Answer 4

我不知道python，但我想试图帮助你：可能还有很多其他更高性能的算法，但我想过这个：它是完全递归的，它应该涵盖所有的情况一个排列。我要开始一个基本的例子：

置换

ABC现在

，这种算法的工作过程是这样：为Length次你右移字母，但最后一个字母将成为第一个（你可以用队列轻松做到这一点）。

回到例子中，我们将有：

• ABC
• BCA
• CAB

现在你重复第一个（也是唯一）的步骤从第二个字母到最后一个字母的子字符串。

不幸的是，用这种算法，你不能考虑重复排列。

Answer 5

如果有很多重复的字母，关键将只产生一次anagram，而不是产生所有可能的排列和消除重复。

这里是一个可能算法只生产每一次字谜：

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（multiset）来保存尚未放置的元素，而不是仅使用列表。

迭代过程中产生的Counter对象的数量肯定是过多的，并且几乎肯定有更快的写入方式;我选择这个版本是因为它的简单性和（希望）其清晰度