所有5个字母的单词都重复3个字符？

Question

我创建了5个循环，遍历字母表中的每个字母，然后将它们全部添加到列表中。然后，我列出该列表，并针对每个字母检查该字母是否具有3个重复字符，然后中断。但是，这显然效率极低，我的计算机花很长时间才能返回结果。有谁对我如何做和改善运行时间有更好的想法？例如：cccde，yxxxz btw我不能导入除数学，随机，字符串之外的其他库

#generate all possible 5 letter combinations without repeats 
    for one in alpha:
        for two in alpha:
            for three in alpha:
                for four in alpha: 
                    for five in alpha:
                        key = str(one+two+three+four+five)
                        if (key in list1) == False:
                            list1.append(key)

    #filter down to ones with three repeated letters:     
    for word in list1:
        for letter in word: 
            if word.count(letter) == 3:
                list2.append(word)
                break```

Answer 1

所有有效字符串最多只能包含3个不同的字母。重复第一个，或者第二个，或者第三个。我们需要进行一些测试，以防止先前生成的字符串再次被添加：

alpha = list('abcdefghijklmnopqrstuvwxyz')

l = []
for one in alpha:
    for two in alpha:
        for three in alpha:
            l.append(one+one+one+two+three)
            if one != two:
                l.append(one+two+two+two+three)
            if two != three:
                l.append(one+two+three+three+three)
print(len(l), l)

Answer 2

您当前算法的最大问题是检查if (key in list1) == False:。没有理由这样做，因为循环中永远不会有任何重复项，这会使您的算法成为O（n ^ 2）而不是O（n），其中n是列表的大小。该代码在合理的时间内运行：

import string

alpha = string.ascii_lowercase
list1 = []

for one in alpha:
    for two in alpha:
        for three in alpha:
            for four in alpha:
                for five in alpha:
                    word = one + two + three + four + five
                    for letter in word:
                        if word.count(letter) == 3:
                            list1.append(word)

print(len(list1))

Answer 3

• 使用字母上的itertools.product生成所有3个字母的字符串，重复3。
• 通过这些排列进行迭代；对于每个字母，将每个字母三倍，给出三个不同的五字母解决方案。例如，从abc中，您将生成aaabc，abbbc和abccc。
• 删除重复项：3个字母的字母加倍（或增加两倍）的单词将产生重复项。例如，aab将以两种不同的方式生成aaaab。

提示是否足够？

Answer 4

我将其分解为更简单的任务。收集所有字母各出现三遍的集合。接收该池中五个字母的所有组合。 Presto

from string import ascii_lowercase
from itertools import combinations
combinations(list(ascii_lowercase*3), 5)