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 倍!
