python - 生成 2 个列表的所有组合(玩游戏)

Question

我试图在 python 中生成 2 个列表 A 和 B 之间的所有可能的组合，但有一些限制。 A 和 B 交替选取值，A 始终先选取。 A 和 B 可能具有重叠的值。如果 A 已经选择了一个值，则 B 无法选择它，反之亦然。

两个列表的长度不必相同。如果一个列表没有可供选择的可用值，那么我将停止生成组合

此外，每个元素选取的元素必须按升序排列，即 A[1] < A[2] < .... A[n]和B[1] < B[2] < .... B[n]哪里A[i]和B[i]是i -A和B分别选取的第一个元素

示例:

A = [1, 2, 3, 4]
B = [2, 5]

我需要的解决方案是

(1), (2), (3), (4),
(1,2), (1,5), (2,5), (3,2), (3,5), (4,2), (4,5),
(1,2,3), (1,2,4), (3,2,4), (1,5,2), (1,5,3), (1,5,4), (2,5,3), (2,5,4), (3,5,4),
(1,2,3,5), (1,2,4,5), (3,2,4,5)
(1,2,3,5,4)

我相信 python 中的 itertools 对此很有用，但我还没有真正弄清楚如何在这种情况下实现它。

到目前为止，我正在解决这个问题:

A = [1, 2, 3, 4]
B = [2, 5]
A_set = set(A)
B_set = set(b)
#Append both sets
C = A.union(B)
for L in range(len(C), 0, -1):
        for subset in itertools.combinations(C, L):
        #Check if subset meets constraints and print it if it does

Answer 1

正如评论中所指出的，这可能过于具体，无法使用 itertools 轻松解决，您应该使用递归(生成器)函数。只需从轮到的列表中选择下一个元素，跟踪已选择的元素，然后再次递归调用该函数，交换和缩短列表并将该元素添加到所选元素集中，直到获得所需的元素数量。

类似这样的东西(这可以通过在两个列表中添加当前索引的参数而不是实际切片递归调用的列表来改进):

def solve(n, lst1, lst2, selected):
    if n == 0:
        yield []
    elif lst1:
        for i, x in enumerate(lst1):
            if x not in selected:
                selected.add(x)
                for rest in solve(n-1, lst2, lst1[i+1:], selected):
                    yield [x] + rest
                selected.remove(x)

或者更简洁一点:

def solve(n, lst1, lst2, selected):
    if n == 0:
        yield []
    elif lst1:
        yield from ([x] + rest for i, x in enumerate(lst1) if x not in selected
                               for rest in solve(n-1, lst2, lst1[i+1:], selected.union({x})))

示例:

A = [1, 2, 3, 4]
B = [2, 5]
result = [res for n in range(1, len(A)+len(B)+1) for res in solve(n, A, B, set())]

之后，结果是:

[[1], [2], [3], [4],
 [1, 2], [1, 5], [2, 5], [3, 2], [3, 5], [4, 2], [4, 5],
 [1, 2, 3], [1, 2, 4], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 5, 3], [2, 5, 4], [3, 2, 4], [3, 5, 4], 
 [1, 2, 3, 5], [1, 2, 4, 5], [3, 2, 4, 5],
 [1, 2, 3, 5, 4]]