获取符合条件的组合

问题：我有一个表，我需要在其中提取行（或列，如果我转置表）的所有有效组合。列中只有值“+”或“-”，并且当组合中的至少一行中有“+”时，组合被认为是有效的，也就是说，所有行中带有“-”的任何组合都是无效的。

示例表：

   Guns  P_01 P_02 P_03 P_04 P_05 P_06 P_07
0  G_01    +    -    +    +    +    -    +
1  G_02    +    +    +    -    +    +    -
2  G_03    -    -    -    +    +    +    +
3  G_04    +    +    +    -    -    -    -
4  G_05    +    +    +    -    -    -    -
5  G_06    -    -    -    +    +    +    +
6  G_07    +    +    +    -    -    -    -

有效组合示例：

0  G_01    +    -    +    +    +    -    +
1  G_02    +    +    +    -    +    +    -

无效组合示例：

3  G_04    +    +    +    -    -    -    -
4  G_05    +    +    +    -    -    -    -

为了获得所有组合，我尝试使用 itertools 组合，并将结果放入列表中：

dfcomb =  [] 
dfcomb = df.apply(lambda r: list(combinations(r, 2)), axis=0)

Output:

         Guns     P_01    P_02    P_03    P_04    P_05    P_06    P_07
0   (G_01, G_02)  (+, +)  (-, +)  (+, +)  (+, -)  (+, +)  (-, +)  (+, -)
1   (G_01, G_03)  (+, -)  (-, -)  (+, -)  (+, +)  (+, +)  (-, +)  (+, +)
2   (G_01, G_04)  (+, +)  (-, +)  (+, +)  (+, -)  (+, -)  (-, -)  (+, -)
3   (G_01, G_05)  (+, +)  (-, +)  (+, +)  (+, -)  (+, -)  (-, -)  (+, -)
4   (G_01, G_06)  (+, -)  (-, -)  (+, -)  (+, +)  (+, +)  (-, +)  (+, +)
5   (G_01, G_07)  (+, +)  (-, +)  (+, +)  (+, -)  (+, -)  (-, -)  (+, -)
6   (G_02, G_03)  (+, -)  (+, -)  (+, -)  (-, +)  (+, +)  (+, +)  (-, +)
7   (G_02, G_04)  (+, +)  (+, +)  (+, +)  (-, -)  (+, -)  (+, -)  (-, -)
8   (G_02, G_05)  (+, +)  (+, +)  (+, +)  (-, -)  (+, -)  (+, -)  (-, -)
9   (G_02, G_06)  (+, -)  (+, -)  (+, -)  (-, +)  (+, +)  (+, +)  (-, +)
10  (G_02, G_07)  (+, +)  (+, +)  (+, +)  (-, -)  (+, -)  (+, -)  (-, -)
11  (G_03, G_04)  (-, +)  (-, +)  (-, +)  (+, -)  (+, -)  (+, -)  (+, -)
12  (G_03, G_05)  (-, +)  (-, +)  (-, +)  (+, -)  (+, -)  (+, -)  (+, -)
13  (G_03, G_06)  (-, -)  (-, -)  (-, -)  (+, +)  (+, +)  (+, +)  (+, +)
14  (G_03, G_07)  (-, +)  (-, +)  (-, +)  (+, -)  (+, -)  (+, -)  (+, -)
15  (G_04, G_05)  (+, +)  (+, +)  (+, +)  (-, -)  (-, -)  (-, -)  (-, -)
16  (G_04, G_06)  (+, -)  (+, -)  (+, -)  (-, +)  (-, +)  (-, +)  (-, +)
17  (G_04, G_07)  (+, +)  (+, +)  (+, +)  (-, -)  (-, -)  (-, -)  (-, -)
18  (G_05, G_06)  (+, -)  (+, -)  (+, -)  (-, +)  (-, +)  (-, +)  (-, +)
19  (G_05, G_07)  (+, +)  (+, +)  (+, +)  (-, -)  (-, -)  (-, -)  (-, -)
20  (G_06, G_07)  (-, +)  (-, +)  (-, +)  (+, -)  (+, -)  (+, -)  (+, -)

但现在我陷入困境，我知道我应该使用循环来验证任何组合是否有效，但我该怎么做呢？

如果您将 + 和 - 视为 True 和 False 并应用or每列的操作：

G_01    +    -    +    +    +    -    +
G_02    +    +    +    -    +    +    -
---------------------------------------
OR      +    +    +    +    +    +    +  ==> All true. This combo is valid

G_04    +    +    +    -    -    -    -
G_05    +    +    +    -    -    -    -
---------------------------------------
OR      +    +    +    -    -    -    -  ==> Not all true. This combo is invalid

唯一剩下的问题是如何快速比较它们。我们可以使用 numpy 的数组广播功能来做到这一点。简而言之，数组广播是对不同大小的数组执行操作的行为：

# When you compare an array to a scalar, the logical action is to compare
# every element of the array that scalar
[a, b, c] > d is equivalent to [a > d, b > d, c > d]

# If you want to compare every element of a list against every element of
# another list, things get a little tricky
[a, b, c] > [d, e] ???

# The trick is to raise the raise the second array up another dimension so you
# you can a comparison matrix. The first array remains 1D, the second array is
# now 2D
[a, b, c] > [[d], [e]]

# One way to visualize it
   d        e
a  a > d    a > e
b  b > d    b > e
c  c > d    c > e

这是您问题的答案：

# Life is a lot easier if you put Guns on the index
df.set_index('Guns', inplace=True)

# A 2D array of True/False
a = df.applymap(lambda x: x == '+').to_numpy()

# A 3D array to be used for in the OR operation
b = a[:, None]

# OR-ing every gun with every other gun
c = np.all(a | b, axis=-1)

# This is what c looks like, with some labels added
#        G_01   G_02   G_03   G_04   G_05   G_06   G_07
#      |------------------------------------------------
# G_01 | False   True  False  False  False  False  False    ==> (G_01, G_02) is valid
# G_02 |  True  False   True  False  False   True  False    ==> (G_02, G_01), (G_02, G_03) and (G_02, G_06) are valid
# G_03 | False   True  False   True   True  False   True
# G_04 | False  False   True  False  False   True  False
# G_05 | False  False   True  False  False   True  False
# G_06 | False   True  False   True   True  False   True
# G_07 | False  False   True  False  False   True  False

# Obviously (G_01, G_02) and (G_02, G_01) are the same combo so we don't need
# to collect both of them. We only need to work with the upper triangle in the
# matrix (`triu` means triangle upper)
valid_combinations = [(df.index[i], df.index[j]) for i,j in np.dstack(np.triu_indices_from(c))[0] if c[i][j]]

由于它使用 numpy 的广播，因此它受益于所有底层矢量化。我在不到 3 秒的时间内运行了 1000 x 1000 数据帧（1M 元素）。

Edit:要扩展它以覆盖任意大小的组合，您只需在每次迭代中不断提高比较矩阵：

def get_valid_combos(df, combo_size=2):
    assert combo_size >= 2, 'combo_size must be at least 2'

    a = df.applymap(lambda x: x == '+').to_numpy()
    result = a

    while combo_size > 1:
        a = a[:, None]
        result = result | a
        combo_size -= 1

    result = result.all(axis=-1)

    # Return True if array is monotonically increasing to avoid duplicates
    # like (G_1, G_2, G_3) and (G_1, G_3, G_2)
    is_increasing = lambda arr: (np.diff(arr) > 0).all()
    valid_indicies = np.array(result.nonzero()).transpose()
    return [tuple(df.index[idx]) for idx in valid_indicies if is_increasing(idx)]

请注意，这个数字呈指数增长。如果你有n枪，需要n ^ combo_size空间和可能n ^ (2 * combo_size)时间。有优化的机会：如果G_1 and G_2进行有效的组合，任何具有这两个的组合也是有效的，因此可以节省我们一些时间。但我现在太懒了。