旋律密码的Hackerrank提交优化

Question

给定来自Hackerrank的问题：

• 密码完全由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 ""

这段代码可以用任何方式进行优化吗？

Answer 1

保持你目前这样做的方式，你可以：

• 将辅音改为字符串。这允许更容易的可读性，并可能提供比列表更好的性能。
• UPPER_SNAKE_CASE中的名称常量。
• 使用itertools.pairwise，您可以删除所有的条形图一个if。这是因为您可以对每个字母进行分类，l in consonants。然后比较它们是否相同。
• 您应该使用一个函数，如它可以更快
• 您应该使用if __name__ == '__main__'守卫。
• 您应该使用print ''.join(letters)，而不是for j in letters: sys.stdout.write(j)。
• 您可以从函数中选择yield，这样如果不够快，就可以对打印进行分组。或者以其他方式使用。

这可能导致：

import itertools

CONSONANTS = 'bcdfghjklmnpqrstvwxz'
VOWELS = 'aeiou'


def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return izip(a, b)


def generate_answers(n):
    consonants = CONSONANTS
    for answer in itertools.product(consonants + VOWELS, repeat=n):
        letter_categories = (l in consonants for l in answer)
        if all(a != b for a, b in pairwise(letter_categories)):
            yield ''.join(answer)


if __name__ == '__main__':
    for answer in generate_answers(int(raw_input().strip())):
        print(answer)

然而，这是基于对itertools.product的低效使用。相反，您希望将参数传递给它，以便它能够高效地创建它们。当n是偶数时，这很容易做到：

def generate_answers(n):
    return chain(product(CONSONANTS, VOWELS, repeat=n//2),
                 product(VOWELS, CONSONANTS, repeat=n//2))

当n是奇数时，有效地做到这一点也是相当容易的。您想做大致相同的事情，但是如果产品的第一项与第一个参数的第一个字符不一样，那么停止循环。所以你可以用：

import itertools

CONSONANTS = 'bcdfghjklmnpqrstvwxz'
VOWELS = 'aeiou'


def product(a, b, repeat):
    if repeat % 2 == 0:
        for ret in itertools.product(a, b, repeat=repeat//2):
            yield ret
    else:
        for ret in itertools.product(b, a, repeat=repeat//2+1):
            if ret[0] != b[0]:
                break
            yield ret[1:]


def generate_answers(n):
    return itertools.chain(product(CONSONANTS, VOWELS, repeat=n),
                           product(VOWELS, CONSONANTS, repeat=n))


if __name__ == '__main__':
    for answer in generate_answers(int(raw_input().strip())):
        print(''.join(answer))