如何在Python中生成只包含'x'、'y'和给定长度n的回文列表？

Question

有没有什么规律可以帮助我创建一个由'X'和'Y'组成的回文字符串？

Answer 1

首先，根据一组字符生成所有可能的字符串：

>>> from itertools import product
>>> characters = ['x','y']
>>> n = 5
>>> [''.join(i) for i in product(characters, repeat=n)]
['xxxxx', 'xxxxy', 'xxxyx', 'xxxyy', 'xxyxx', 'xxyxy', 'xxyyx', 'xxyyy', 'xyxxx', 'xyxxy', 'xyxyx', 'xyxyy', 'xyyxx', 'xyyxy', 'xyyyx', 'xyyyy', 'yxxxx', 'yxxxy', 'yxxyx', 'yxxyy', 'yxyxx', 'yxyxy', 'yxyyx', 'yxyyy', 'yyxxx', 'yyxxy', 'yyxyx', 'yyxyy', 'yyyxx', 'yyyxy', 'yyyyx', 'yyyyy']

然后筛选出不是回文的字符串：

>>> n = 4
>>> [''.join(i) for i in product(characters, repeat=n) if i[:n/2] == i[::-1][:n/2]]
['xxxx', 'xyyx', 'yxxy', 'yyyy']
>>> n = 5
>>> [''.join(i) for i in product(characters, repeat=n) if i[:n/2] == i[::-1][:n/2]]
['xxxxx', 'xxyxx', 'xyxyx', 'xyyyx', 'yxxxy', 'yxyxy', 'yyxyy', 'yyyyy']

如果你不喜欢在列表推导式中使用条件判断，可以用 filter() 函数：

>>> from itertools import product
>>> characters = ['x','y']
>>> n = 5
>>> def ispalindrome(x): return x[:n/2] == x[::-1][:n/2];
>>> filter(ispalindrome, [''.join(i) for i in product(characters, repeat=n)])
['xxxxx', 'xxyxx', 'xyxyx', 'xyyyx', 'yxxxy', 'yxyxy', 'yyxyy', 'yyyyy']

Answer 2

假设 n 是一个偶数。我们要生成每个长度为 n/2 的字符串，这些字符串只包含 x 和 y，然后把它们的镜像（反转的样子）加到后面，这样就能得到一个回文字符串。

练习 1：证明这样的方法可以生成所有长度为 n 的回文字符串。

练习 2：想一想，当 n 是奇数时该怎么做。