我正在尝试获取一个列表中所有值的组合，对于这些值，另一个列表的相应值之和不会超过某个限制。例如，我有一些作业要批量生产，但该批次的容量有限，这意味着只有特定的作业组合才能放在一起，这样它们的大小就不会超过批次的容量。
假设我有定义为作业1、作业3和作业5的作业，我有以下列表：
jobs = [1,3,5]
如果作业1的大小为1，作业3的大小为3，作业5的大小为2，则我有以下列表：
jobSize = [1,3,2]
如果我的批次最大容量为5，这意味着所需的输出如下：
combinations = [(1),(3),(5),(1,3),(1,5),(3,5)]
#here I use the name/number of the jobs, and (1,3,5) not included cause total size of 5 is exceeded
根据我所看到的，使用itertools的组合可以做一些类似的事情(不完全相同(，比如这里解释的Python中的Powersets使用iterttools或这里如何获得列表元素的所有可能组合？，但这肯定没有我希望的那么有效。
我还尝试了一些关于itertools.product和np.where的东西，就像这里解释的Python Numpy：Corralien从数组或标量的所有组合，但再一次，这不是我所需要的，并且需要大量的后处理操作，最终速度太慢。
我的想法是，以某种方式使用numpy数组是可能的，因为这是我认为这是快速的唯一方法。有人知道吗？
我认为最简单的方法是使用递归函数。您从列表中删除一个作业，然后在剩余的子列表上运行该函数。然后，将子列表的结果与第一个作业相应地组合起来。
这样，如果一个组合无效——例如(1，2，3(，当max为5时——它将不会显示在子列表的结果中，因此所有包含(1，3(的较长组合都将被删除。
这可以通过以下方式加以改进：
- 从递归变为迭代
- 使用多处理。例如，这给出了6个需要与子列表处理结果组合的组合，而不是1个作业-3个第一个作业。这可以分为同时运行的进程
- 利用作业可能具有相同CCD_ 1的事实。在这种情况下，结果是对称的
代码：
import sys
import time
from collections import namedtuple
def print_job(self):
#return f'( /{self.job_name}/ {self.size} )'
return str(self.job_name)+' ('+str(self.size)+')'
def print_solution(self):
return ' '.join([str(job) for job in self.jobs]) # +'n'
Job = namedtuple('Job', ['job_name','size'])
Solution = namedtuple('Solution', ['jobs', 'Size'])
Job.__repr__ = print_job
Solution.__repr__ = print_solution
########### main function #################################
def find_sets(job_list, max_size):
first_job = job_list[0]
new_solutions = []
if len(job_list) > 1:
other_solutions = find_sets(job_list[1:], max_size)
for solution in other_solutions:
if solution.Size + first_job.size <= max_size:
new_solution = Solution(solution.jobs + [first_job], solution.Size + first_job.size)
new_solutions.append(new_solution)
else:
other_solutions = []
if first_job.size <= max_size:
new_solutions.append(Solution([first_job], first_job.size))
return other_solutions + new_solutions
def find_all_job_sets(jobs='ABC', jobSize = (1,3,2), max_size=5, show_progress=True):
sys.setrecursionlimit(1500)
if (len(jobs) != len(jobSize)):
print('Number of jobs and jobSizes must match.')
exit(1)
jobList = list(Job(name, size) for name, size in zip(jobs, jobSize))
start = time.time()
results = find_sets(jobList, max_size)
end = time.time()
print(results)
print(f'Number of sets: {len(results)}')
print(f'Time: {int((end - start) * 100) / 100} seconds')
find_all_job_sets(jobs='ABCDE', jobSize=[1,2,3,4,5], max_size=5)
输出：
[E (5), D (4), C (3), C (3) B (2), B (2), D (4) A (1), C (3) A (1), B (2)
A (1), A (1)]
Number of sets: 9
示例：
find_all_job_sets(jobs=[f'J{i}' for i in range(100)],
jobSize=list(range(20,120)), max_size=200)
输出：
...
J2 (22) J1 (21) J0 (20), J8 (28) J6 (26) J5 (25) J4 (24) J3 (23) J2 (22) J1 (21) J0 (20), J7 (27) J6 (26) J5 (25) J4 (24) J3 (23) J2 (22) J1 (21) J0 (20), J6 (26) J5 (25) J4 (24) J3 (23) J2 (22) J1 (21) J0 (20), J5 (25) J4 (24) J3 (23) J2 (22) J1 (21) J0 (20), J4 (24) J3 (23) J2 (22) J1 (21) J0 (20), J3 (23) J2 (22) J1 (21) J0 (20), J2 (22) J1 (21) J0 (20), J1 (21) J0 (20), J0 (20)]
Number of sets: 1462601
Time: 3.11 seconds
200个工作列表：
find_all_job_sets(jobs=[f'J{i}' for i in range(200)],
jobSize= [12, 13, 14, 15, 16] + list(range(105, 300)), max_size=500)
输出：
...
J5 (105) J4 (16) J3 (15) J2 (14) J1 (13) J0 (12), J6 (106) J5 (105) J4 (16) J3 (15) J2 (14) J1 (13) J0 (12), J5 (105) J4 (16) J3 (15) J2 (14) J1 (13) J0 (12), J4 (16) J3 (15) J2 (14) J1 (13) J0 (12), J3 (15) J2 (14) J1 (13) J0 (12), J2 (14) J1 (13) J0 (12), J1 (13) J0 (12), J0 (12)]
Number of sets: 3985093
Time: 7.42 seconds
您可以使用0/1的2D矩阵来处理此问题，其中1表示选择运行作业：
from sklearn.utils.extmath import cartesian
jobs = [1,3,5,7,9]
jobSize = [1,3,2,2,5]
target = 5
# produce all combinations of 0/1
# 1 column per job
m = cartesian([[0,1]]*len(jobSize))
# compute sum of job costs
total = (jobSize*m).sum(axis=1)
# get combinations with total cost ≤ target
idx = np.nonzero(total<=target)[0]
out = m[idx]
输出：
# job 1 3 5 7 9
array([[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 0]])
如果您希望输出为列表，您可以进一步使用itertools.compress:
from itertools import compress
out = [list(compress(jobs, l)) for l in m[idx]]
输出：
[[], [9], [7], [5], [5, 7], [3], [3, 7], [3, 5], [1], [1, 7], [1, 5], [1, 5, 7], [1, 3]]