所有三个字母重复的五个字母吗?

问题描述 投票:1回答:5

我创建了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```
python for-loop
5个回答
2
投票

所有有效字符串最多只能包含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)

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))

1
投票
  • 使用字母上的itertools.product生成所有3个字母的字符串,重复3。
  • 通过这些排列进行迭代;对于每个字母,将每个字母三倍,给出三个不同的五字母解决方案。例如,从abc中,您将生成aaabcabbbcabccc
  • 删除重复项:3个字母的字母加倍(或增加两倍)的单词将产生重复项。例如,aab将以两种不同的方式生成aaaab

提示是否足够?


0
投票

我有一个建议,只有一个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)

0
投票

这里尝试仅用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]
© www.soinside.com 2019 - 2024. All rights reserved.