如何编辑此算法,使其在不替换或重用元素的情况下创建组合?

2024-03-29 12:59:41 发布

您现在位置:Python中文网/ 问答频道 /正文

我对计算机科学很陌生,这是我的第一个程序。我编写了一个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


Tags: ofinimport程序forvaluedef标签
1条回答
网友
1楼 · 发布于 2024-03-29 12:59:41

下面是我在评论中提到的一种线性规划方法:

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()将生成一个可行的解决方案,但是因为您需要所有可行的解决方案,所以在while循环中调用prob.solve()。只要它能返回一个可行的解(==1),就继续循环。但是在每次迭代中,我们应该排除当前的解决方案,这样我们的搜索空间就会减少。这是在最后一行完成的。例如,如果在当前的解决方案中我们有var00var04var07,那么对于随后的问题,它们的和应该小于3(所有三个不应该同时为1)。如果您运行这个,它将为您的问题生成所有可能的解决方案。你知道吗

以下是前五项:

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

这些是他们的价值观:

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

相关问题 更多 >