Skip to main content
 首页 » 编程设计

Python Itertools 代码优化

2025年02月15日8artech

Given question (the contest is now over)

  • 密码由n个小写英文字母组成。
  • 密码是悦耳的,意思是辅音只能在旁边 元音和元音只能紧挨着辅音。示例:bawahaha
  • 密码不能包含字母y(因为它既是 辅音和元音)。
  • 密码的第一个字母可以是 元音或辅音。

给定密码的长度n,

打印所有满足上述条件的可能密码。

输入格式

输入行包含整数(密码的长度)。

约束

输出格式

打印每个可能的密码,每行一个。密码的顺序无关紧要。

我的 Python 代码:

import sys 
import itertools 
 
n = int(raw_input().strip()) 
 
consonants = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z'] 
vowels = ['a', 'e', 'i', 'o', 'u'] 
 
 
test4 = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z', 'a', 'e', 'i', 'o', 'u'] 
answer = set(itertools.product(test4, repeat=n)) 
 
for letters in answer: 
    for j in xrange(len(letters)): 
        flag = 1 
        if j != len(letters) - 1: 
            if letters[j] in vowels and letters[j+1] in vowels: 
                flag = 0 
                break 
            if letters[j] in consonants and letters[j+1] in consonants: 
                flag = 0 
                break 
 
    if flag: 
        for j in letters: 
            sys.stdout.write(j) 
        print "" 

有更好的方法吗?

请您参考如下方法:

当然有更好的方法(如果您的意思是更快)。您可以生成一个 itertools.product,您不必在其中“丢弃”项目。

您可以简单地创建一个 product 的 vowel, consonant, vowel, consonant, ... (交替两个列表 n 次)和一个以 consonant, vowel, consonant, vowel, ... 开头的。返回的项目将始终满足条件,因此需要做的就是打印它们。

import itertools 
 
def alternating(seq1, seq2, length): 
    """Generator that alternatingly yields seq1 and seq2, `length` times""" 
    assert length >= 0 
    for _ in range(length // 2): 
        yield seq1 
        yield seq2 
    if length % 2 == 1: 
        yield seq1 
 
consonants = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z'] 
vowels = ['a', 'e', 'i', 'o', 'u'] 
 
n = int(raw_input().strip()) 
 
# Starts with vowel 
for comb in itertools.product(*list(alternating(vowels, consonants, n))): 
    print(''.join(comb)) 
 
# Starts with consonant 
for comb in itertools.product(*list(alternating(consonants, vowels, n))): 
    print(''.join(comb)) 

这样您就可以减少可能的候选人数量。

您的方法给出了 25**n 个项目,而新方法只生成了 2 * 5**(n//2)*20**(n//2)(如果 n 偶数)或 5**(n//2 + 1) * 20 ** (n//2) + 5**(n//2) * 20 ** (n//2 + 1)(如果 n 为奇数)项。

对于 n=5 这意味着:最初从 product 生成 9765625 项(将近 1000 万!)现在只会生成 250000 项。即使忽略(可能非常昂贵)检查您的序列是否满足问题条件(现在已过时),您在 product 中生成的项目多了 40 倍!