python - 根据条件排列旗帜中的条纹

Question

我需要有关如何找到在条件下在旗帜中排列白色、蓝色和红色三种颜色条纹的方法数量的策略的帮助:

1. 相同颜色的条纹不能并排放置。
2. 蓝色条纹必须始终位于白色和红色之间或红色和白色之间。

对于n=3(flag中只能有三个条纹)，输出为4

这里是问题的进一步链接。 http://acm.timus.ru/problem.aspx?space=1&num=1225

Answer 1

首先生成所有可能的条纹组合:

import itertools
stripes = list(itertools.product('RBW',repeat=3))
print(stripes)

输出:

[('R', 'R', 'R'), ('R', 'R', 'B'), ('R', 'R', 'W'), ('R', 'B', 'R'), ('R', 'B', 'B'), ('R', 'B', 'W'), ('R', 'W', 'R'), ('R', 'W', 'B'), ('R', 'W', 'W'), ('B', 'R', 'R'), ('B', 'R', 'B'), ('B', 'R', 'W'), ('B', 'B', 'R'), ('B', 'B', 'B'), ('B', 'B', 'W'), ('B', 'W', 'R'), ('B', 'W', 'B'), ('B', 'W', 'W'), ('W', 'R', 'R'), ('W', 'R', 'B'), ('W', 'R', 'W'), ('W', 'B', 'R'), ('W', 'B', 'B'), ('W', 'B', 'W'), ('W', 'W', 'R'), ('W', 'W', 'B'), ('W', 'W', 'W')]

然后丢弃不满足要求的，首先:没有2个相同的颜色相邻，让make函数检查:

def no_two(x):
    return all([i[0]!=i[1] for i in zip(x[1:],x[:-1])])

然后按照以下方式使用它:

stripes = [s for s in stripes if no_two(s)]
print(stripes)

输出:

[('R', 'B', 'R'), ('R', 'B', 'W'), ('R', 'W', 'R'), ('R', 'W', 'B'), ('B', 'R', 'B'), ('B', 'R', 'W'), ('B', 'W', 'R'), ('B', 'W', 'B'), ('W', 'R', 'B'), ('W', 'R', 'W'), ('W', 'B', 'R'), ('W', 'B', 'W')]

然后我们需要函数来检查蓝色是否总是在白色和红色之间或红色和白色之间:

def blue_between(x):
    if x[0]=='B':
        return False
    if x[-1]=='B':
        return False
    for i in zip(x[:-2],x[1:-1],x[2:]):
        if i[1]=='B':
            if not ((i[0]=='R' and i[2]=='W') or (i[0]=='W' and i[2]=='R')):
                return False
    return True

并按照以下方式使用它:

stripes = [s for s in stripes if blue_between(s)]
print(stripes)

输出:

[('R', 'B', 'W'), ('R', 'W', 'R'), ('W', 'R', 'W'), ('W', 'B', 'R')]

注意使用 zip 和索引切片来获取当前 strip 和下一个或上一个和下一个 strip 。