我有一個 16 列和 22 行的陣列。
請建議如何使用以下規則找到所有可能的組合：
- 我每行不能選擇超過 1 個值
- 列索引的總和應等于 16（1 1 14,15 1,2 2 2 2 2 6 等）
- 選定單元格中的值總和應介于 39 和 42 之間
例如，我選擇了 5 種組合：
- 第一個：值總和(8.4 4.8 5.7 4 3.6 3.8=41.3) 列值總和 = 3 3 2 2 2 2 2=16
- 2nd: sum of values(36.7) sum of column values = 3 3 3 3 3 1 = 16
- 第 3：值總和 (40.8) 列值總和 = 3 3 3 7 = 16
- 第 4 位：值總和 (41.7) 列值總和 = 3 3 3 7 = 16
- 5h 值總和(41) 列值總和 = 16 = 16
- 等等
我找到了如何獲取所有可能的列組合：import 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 行的陣列
源表如下所示：
紅色是大于 42 的數字
其他 5 種顏色是可能的組合，總和在 39 到 42 之間
| col1 | col2 | col3 | col4 | col5 | |
|---|---|---|---|---|---|
| 第 1 行 | 2 | 4 | 7 | 9 | 11 |
| 第 2 行 | 3 | 6 | 8 | 11 | 14 |
| 第 3 行 | 2 | 5 | 7 | 10 | 12 |
| 第 4 行 | 3 | 6 | 9 | 11 | 14 |
| 第 5 行 | 2 | 4 | 6 | 8 | 10 |
| 第 6 行 | 2 | 4 | 5 | 7 | 9 |
- 條件1，列索引之和為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 個值， 1 個值 col1 和 2 個來自 col2 的值，3 個來自 col1 的值和 1 個來自 col2 的值，等等
- 條件2：找到除同一行的單元格編號之外的所有可能的列項之間的總和組合（例如，對于（1,4）：2 9在同一行需要跳過它，2 11,2 10,2 11,2 8,2 7；3 9,3 11 在同一行，需要跳過它 3 10, 3 11,3 8,3 7 等）
- 條件 3：例如，專案總和不應超過 11，所以我應該只接受上一步中的 2 8、2 7 和 3 7
輸出應該像 (row5,col5), (row6,col5), [(row1,col1)&(row5,col4)], [(row1,col1)&(row6,col4) 等
uj5u.com熱心網友回復：
生成所有可能的行/列組合然后檢查生成串列的總和是非常低效的。所需測驗的數量非常大。例如，如果您只想測驗所有可能行中的 3 列（2、5、9），那么您可以以 22!/(3!*(22-3)!) = 1540 種方式選擇行。如果您想在所有可能的行中測驗 11 列（1、1、1、1、1、1、1、1、1、1、6），那么您可以選擇 22!/(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 檔案只包含沒有任何標題行的資料。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/473538.html