python - 我该如何编辑这个算法，以便它在不替换或重用元素的情况下创建组合？

Question

我是计算机科学的新手 - 这是我的第一个程序。我编写了一个 python 程序，它从 excel 工作表“Labels”:“Values”中获取两列中的数据，并将它们重新配置为标签列表，其各自的值总和为 30。每个标签都是唯一的，只出现一次，但不同的标签可以具有相同的值。

但是，当我第一次应用我的程序时，运行时间将近 30 分钟，因为该算法正在创建所有可能的标签组合。显然给定 50 个值小于 10 的标签，这是很多可能的组合。

我需要一些帮助来编辑我当前的算法，以便它创建独特的组。使用标签后，我不希望它出现在任何其他组中。

目前我的代码是这样的:

def combinator(X): #this function pulls two lists together to create a dictionary
  from xlrd import open_workbook
  wb = open_workbook(X)
  L = []
  P = []
  for s in wb.sheets(): 
      for col in range(s.ncols):
          for row in range(s.nrows):
              if row !=0:
                  l = s.cell(row,0).value
                  L.append(l)

                  p = s.cell(row,1).value
                  P.append(p)
  Lots = L[0:(len(L)/2)]
  Pallets = P[0:(len(L)/2)]
  D = dict(zip(Lots,Pallets))
  return D


def grouper(D, N):#this finds combinations of 30 and puts them in groups
  from itertools import combinations
  groups_of_thirty = []

  for l in range(0, len(D)):
      for y in combinations(D.items(), l):
          keys = []
          sum = 0

          for key, value in y:
              keys.append(key)
              sum += value

          if sum == N:
              groups_of_thirty.append(keys)

  flattened = [v for flat in groups_of_thirty for v in flat]
  K = D.keys()
  s = set(K)
  remainder = list(s - set(flattened))
  list(groups_of_thirty)
  return groups_of_thirty, \
       remainder


def transposer(G):#this exports the final list into each cell and writes  the spreadsheet as a csv to a different directory.
    import os
    os.chdir(Q)
    import csv
    with open(O, "wb") as f:
        writer = csv.writer(f)
        str(writer.writerows(G))
    return

transposer(grouper(combinator(I),N))

将不胜感激对此的任何帮助 - 首选逻辑或伪代码，但一些具有不常见语法的指针会有所帮助，因为我是新手。

谢谢!

编辑:这是 Excel 工作表中示例数据的屏幕截图。

Screenshot of Excel sheet with Input and Desired Output

Answer 1

这是我在评论中提到的线性规划方法:

import pandas as pd
from pulp import *
import random
random.seed(0)
num_items = 50
labels = ['Label{0:02d}'.format(i) for i in range(num_items)]
values = [random.randint(5, 30) for _ in range(num_items)]
df = pd.DataFrame({'Value': values}, index=labels)
feasible_solutions = []
var = LpVariable.dicts('x', labels, 0, 1, LpInteger)
prob = pulp.LpProblem('Fixed Sum', pulp.LpMinimize)
prob += 0
prob += lpSum([var[label] * df.at[label, 'Value'] for label in labels]) == 30

while prob.solve() == 1:
    current_solution = [label for label in labels if value(var[label])]
    feasible_solutions.append(current_solution)
    prob += lpSum([var[label] for label in current_solution]) <= len(current_solution) - 1

labels 是包含标签的常规列表，values 是 5 到 30 之间的随机整数。它以空集开头。

此代码中最重要的元素之一是 var。它是取值 0 或 1 的决策变量。当您在解决方案中包含特定标签时，它取值 1，否则它等于零。

例如，假设您有此列表 [12, 7, 5, 13]。这里，对于可能的解决方案var00 (12)，var02 (5) 和var03 (13) 可以取值1。

下一行创建一个线性规划问题。我们指定一个任意目标函数 (prob += 0)，因为我们没有最小化或最大化任何函数 - 我们试图找到所有可能的解决方案。

这些解决方案应满足下一行中的约束条件。在这里，var[label] 是我提到的二元决策变量。如果它包含在解决方案中，则它取值 1，然后 1 乘以它的值。所以我们只对集合中包含的项目的值求和。它们的总数应等于 30。这里，prob.solve() 会生成一个可行的解决方案，但由于您需要所有可行的解决方案，因此您可以调用 prob.solve()一个 while 循环。只要能返回一个可行解(==1)就继续循环。但是在每次迭代中，我们都应该排除当前的解决方案，以便减少我们的搜索空间。它由最后一行完成。例如，如果在当前解决方案中我们有var00、var04和var07，对于后续问题(所有三个不应同时为 1)。如果您运行它，它将为您的问题生成所有可能的解决方案。

这是前五个:

feasible_solutions[:5]
Out: 
[['Label00', 'Label47'],
 ['Label17', 'Label46'],
 ['Label42', 'Label45'],
 ['Label03', 'Label13', 'Label47'],
 ['Label02', 'Label03', 'Label48']]

这些是他们的值(value)观:

Out: [[17, 13], [9, 21], [11, 19], [6, 11, 13], [18, 6, 6]]