如何找到可能的组合

Question

我有一个 16 列和 22 行的数组。

请告知如何使用以下规则找到所有可能的组合：

我每行只能选择 1 个值
列索引的总和应等于 16（1+1+14,15+1,2+2+2+2+2+6 等）
所选单元格中的值总和应介于 39 和 42 之间

例如我选择了 5 种组合：

1st: Sum of values(8.4+4.8+5.7+4+3.6+3.8=41.3) Sum of column values = 3+3+2+2+2+2+2=16
第二个：值的总和(36.7) 列值的总和 = 3+3+3+3+3+1 = 16
3rd: sum of values (40.8) 列值之和 = 3+3+3+7 = 16
4th: sum of values (41.7) 列值之和 = 3+3+3+7 = 16
5h 值总和(41) 列值总和 = 16 = 16
等等

我找到了如何获得所有可能的列组合：导入 itertools

def summs(answer, *dig):

    res = []
    for i in range(1, answer + 1):
        for j in itertools.combinations_with_replacement(list(dig), i):
            if sum(list(j)) == answer:
                res.append(j)
    return res

现在我有 231 个不同的列索引组合，每个总和等于 16。

[(1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 9), (8 , 8), (1, 1, 14), (1, 2, 13), (1, 3, 12), (1, 4, 11), (1, 5, 10), (1, 6, 9 ), (1, 7, 8), (2, 2, 12), (2, 3, 11), (2, 4, 10), (2, 5, 9)... 等等

现在我正在尝试查找以上列索引组合的所有行总和组合：

例如对于 (1,15) 数组（2 列，22 行）我应该找到所有的总和组合，除了相同的行总和（第 1 和 2、2 和 3 等行）

对于 (1, 5, 10) 其 3 列 22 行的数组

依此类推直到 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) 这是 16 列的数组，22行

来源 table 看起来像这样：

红色是大于 42 的数字

其他 5 种颜色可能的组合，总和在 39 到 42 之间

	col1	col2	col3	col4	col5
row1	2	4	7	9	11
row2	3	6	8	11	14
row3	2	5	7	10	12
row4	3	6	9	11	14
row5	2	4	6	8	10
row6	2	4	5	7	9

条件一，列索引之和为5：可能的组合有[(5),(1, 4), (2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 1, 2), (1, 1, 1, 1, 1)], 这意味着您可以从第 5 列中选择值，或者从 col1 中选择 1 个值，从 col4 中选择 1 个值，或者从 col1 中选择 2 个值，从 col3 中选择 1 个值，从 col2 中选择 1 个值和 2 个值，从 col1 中选择 3 个值，从 col2 中选择 1 个值，等等
条件二：找出列之间所有可能的总和组合同一行中除单元格编号外的项目（例如，对于 (1,4)：2+9 in 同一行跳过，2+11, 2+10, 2+11,2+8,2+7； 3+9,3+11 英寸同一行，请跳过它 3+10、3+11,3+8,3+7 等）
条件3:sum items 不能超过 11 例如，所以我应该只接受上一步的 2+8、2+7 和 3+7

输出应该像 (row5,col5), (row6,col5), [(row1,col1)&(row5,col4)], [(row1,col1)&(row6,col4) 等

Answer 1

生成 row/columns 所有可能的组合然后检查生成列表的总和是非常低效的。所需的测试数量非常大。例如，如果您只想测试所有可能行中的 3 列 (2、5、9)，那么您可以 select 行 22!/(3!*(22-3)!) = 1540 种方式.如果你想在所有可能的行中测试 11 列（1、1、1、1、1、1、1、1、1、1、6），那么你可以在 22 中 select 行！/（ 11!*11!) = 705432 种方式。所以，这样你将需要测试数千万个组合。

相反，您可以制定递归解决方案，当您知道解决方案不可行时会很快失败：

import pandas as pd

def find_combinations(df, from_row, current_sum, current_column_sum,
         target_sum_min, target_sum_max, target_column_sum, cells_list):
    """    
    :param df: the dataframe  
    :param from_row: zero-based row in which to perform the search
    :param current_sum: current sum of selected cells above this row
    :param current_column_sum: current sum of column numbers
    :param target_sum_min: minimum required sum of cells 
    :param target_sum_max: maximum required sum of cells
    :param target_column_sum: required sum of column numbers
    :param cells_list: list of selected cells above this row  
    """

    if from_row >= len(df) or \
       current_sum > target_sum_max or \
       current_column_sum >= target_column_sum :
       return

    max_column = max(len(df.columns), target_column_sum - current_column_sum)
    for column in range(max_column):
        number = df.iloc[from_row][column]
        new_sum = current_sum + number

        if new_sum > target_sum_max:
            break

        if target_sum_min <= new_sum <= target_sum_max and \
            current_column_sum + column + 1 == target_column_sum:
            print([*cells_list, (from_row + 1, column + 1)])

        find_combinations(df, from_row + 1, new_sum, current_column_sum + column + 1,
            target_sum_min, target_sum_max, target_column_sum,
            [*cells_list, (from_row + 1, column + 1)])

    find_combinations(df, from_row + 1, current_sum, current_column_sum,
        target_sum_min, target_sum_max, target_column_sum,
        cells_list)



df = pd.read_csv("data.csv", header=None)

find_combinations(df, 0, 0.0, 0, 39.0, 42.0, 16, [])

PS。我使用 OCR 从您的图像中提取文本数据，所以我的 data.csv 文件只包含没有任何 header 行的数据。

如何找到可能的组合

how to find possible combinations

python

arrays

numpy