条件下旗帜条纹的排列

Question

我需要一个策略来帮助我找到在国旗上排列白色、蓝色和红色三条条纹的方法，条件是：

1. 同一颜色的条纹不能并排放置。你知道吗
2. 蓝色条纹必须始终放在白色和红色之间或红色和白色之间。你知道吗

对于n=3（标志中只能有三个条纹），输出为4

下面是问题的链接，以供进一步讨论。 http://acm.timus.ru/problem.aspx?space=1&num=1225

Answer 1

可以对生成器使用递归：

def flags(d, c = []):
   if len(c) == 3:
      yield c
   else:
      for i in d:
         if (c and c[-1] != i and (True if i != 'B' else len(c) == 1) and ('B' not in c or i not in c)) or (not c and i != 'B'):
            yield from flags(d, c+[i])


print(list(flags(['R', 'W', 'B'])))

输出：

[['R', 'W', 'R'], ['R', 'B', 'W'], ['W', 'R', 'W'], ['W', 'B', 'R']]

Answer 2

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

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个颜色相同的相邻物，让功能检查一下：

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和索引切片来获取当前条带和下一条带或上一条带和下一条带。你知道吗

Answer 3

使用itertools.product获取所有可能的组合，使用itertools.groupby检查彼此之间是否没有任何相同颜色的条纹：

from itertools import product, groupby

colors = [1, 2, 3]  # 1 - red, 2 - blue, 3 - white
n = 3

output = []
for c in product(colors, repeat=n):
    # do we have consecutive colors?
    if max(sum(1 for _ in g) for _, g in groupby(c)) > 1:
        continue
    # is blue color on any end?
    if c[0] == 2 or c[-1] == 2:
        continue
    # is blue color between same colors?
    if any(c[i-1] == c[i+1] for i, v in enumerate(c) if v==2):
        continue
    output.append(c)

from pprint import pprint
pprint(output, width=30)

印刷品：

[(1, 2, 3),
 (1, 3, 1),
 (3, 1, 3),
 (3, 2, 1)]