我创建了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```
所有有效字符串最多只能包含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)
您当前算法的最大问题是检查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))
itertools.product
生成所有3个字母的字符串,重复3。abc
中,您将生成aaabc
,abbbc
和abccc
。aab
将以两种不同的方式生成aaaab
。提示是否足够?
我有一个建议,只有一个for循环,在我的PC上相当快。
from itertools import product, permutations
import string
letters = list(string.ascii_lowercase)
for repeated in letters:
letters.remove(repeated)
print(list(map(list, map(permutations, product(letters, letters, [repeated], [repeated], [repeated])))))
letters.append(repeated)
这里尝试仅用4行:
# Start with set of all letters
s = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}
# Get all combinations of 5 letters
allcombinations = [(a,b,c,d,e) for a in s for b in s for c in s for d in s for e in s]
# Transform to list
biglist = list(allcombinations)
# Filter for only those that have 3 or more repeats
result = [list(filter(lambda x:x.count(x)>=3, biglist)) for x in s]