我有13份属于不同组别的名单。
A组（名单1）
B组(名单2)、(名单3)、(名单4)、(名单5)、(名单6)
C组(名单7)、(名单8)、(名单9)、(名单10)、(名单11)
D组(名单12)、(名单13)
所有的组别加起来的总和必须是1。
A组的取值范围为0-0.7。
B组的取值范围为0-0.6
C组的取值范围为0-0.9
D组可以从0-0.1中取值。
我想找到这些列表在不超过其组别限制的情况下可以进行的所有不同组合。
例如，我想找到这些列表在不超过其组别限制的情况下可以做出的所有不同组合。
如果一个组合List2元素=0. 6, List3, List4, List5和List6必须是0.
有什么简单的方法吗？(我可以用R或Python)
列表取值从 0 到其组的极限，增量为 0。.1)
# i.e.
List1=[0.0,0.1,0.2,...,0.7]
List2 = [0.0,0.1,0.2,...,0.6]
# etc.
按照我的建议 评论 我们可以用 Google OR-工具 是为了解决这样的优化问题。我将尝试分解每一步，使其尽可能清晰，并展示如何扩展以满足您的需求。
from ortools.sat.python import cp_model
model = cp_model.CpModel()
class Data:
def __init__(self, name, ub, model):
self.name = name
self.ub = ub
self.model = model
def make_var(self, repeat):
vars = [self.model.NewIntVar(0, self.ub, f"{self.name}{i}") for i in range(repeat)]
return vars
我们定义一个类。Data 它将保存每个数组的信息。它将包含变量的名称、上界、以及使用该变量的模型的引用。我们还定义了一个函数。make_var 这将为模型创建一个整数变量来求解。
如果你从最高层次考虑，你的模型实际上归结为以下约束。
a + b1 + b2 + b3 + b4 + b5 + c1 + c2 + c3 + c4 + c5 + d1 + d2 == 100
每一组数组都有自己的条件要满足 但从最高层次来看，这就是我们要解决的问题。make_var 将创建每个变量，并将其附加到模型中。如下图所示。
# Variables
a = Data("a", 70, model)
var_a = a.make_var(1)
b = Data("b", 60, model)
var_b = b.make_var(5)
c = Data("c", 90, model)
var_c = c.make_var(5)
d = Data("d", 10, model)
var_d = d.make_var(2)
接下来我们将添加我们的约束条件，每组数组都要遵守。
# Constraints
model.Add(sum(var_a) <= 70)
model.Add(sum(var_b) <= 60)
model.Add(sum(var_c) <= 90)
model.Add(sum(var_d) <= 10)
model.Add(sum(var_a) + sum(var_b) + sum(var_c) + sum(var_d) == 100)
之后，我们将定义一个类，它将打印我们的解决方案，以及限制我们想要返回的解决方案的数量。这是可配置的，你可以根据自己的需要进行修改。这个类是一个修改过的版本，它可以在以下网站找到 此处.
class VarArraySolutionPrinterWithLimit(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables, limit):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
self.__solution_limit = limit
def on_solution_callback(self):
self.__solution_count += 1
for v in self.__variables:
for val in v:
print('%s = %i' % (val, self.Value(val)), end=' ')
print()
if self.__solution_count >= self.__solution_limit:
print('Stop search after %i solutions' % self.__solution_limit)
self.StopSearch()
def solution_count(self):
return self.__solution_count
最后我们解决你的问题的解决方案。
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinterWithLimit([var_a, var_b, var_c, var_d], 10)
status = solver.SearchForAllSolutions(model, solution_printer)
a0 = 0 b0 = 10 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 0
a0 = 0 b0 = 9 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 1 d1 = 0
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 10 d1 = 0
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 9 d1 = 1
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 10
a0 = 0 b0 = 0 b1 = 1 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9
a0 = 0 b0 = 0 b1 = 0 b2 = 1 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 1 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 1 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9
a0 = 0 b0 = 1 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9
Stop search after 10 solutions
我将限制设置为10个解决方案，但如前所述，你可以根据需要更改。它花了大约9毫秒来获得解决方案，所以对于你的使用情况来说，这应该是有效和快速的工作。
我使用的是ints而不是floats，所以例如4代表4%）。
基本思路是找到4个数字 a,b,c,d (其中每个都满足组的约束)，加起来是100。这一部分是我用蛮力完成的，但可以优化。然后，对于每一个这样的4个数字的列表，将其组合成 a 用所有的方法来选择5个数字的总和。b，所有选择5个数字的方法，其总和为 c，以及所有的方法来选择2个数字的总和。d. 我不想说太多的数学问题，但请看维基百科上的文章。明星和酒吧 解压以下代码，其中包含一个计算组合的函数和一个生成组合的生成器。
import itertools, math
def count_combos():
count = 0
for a,b,c,d in itertools.product(range(71),range(61),range(91),range(11)):
if a+b+c+d == 100:
count += math.comb(b+4,4)*math.comb(c+4,4)*(d+1)
return count
#uses stars and bars to enumerate k-tuples of nonnegative numbers which sum to n:
#assumes k > 1
def terms(n,k):
for combo in itertools.combinations(range(n+k-1),k-1):
s = [combo[0]]
for i in range(1,k-1):
s.append(combo[i]-combo[i-1]-1)
s.append(n+k - 2 - combo[k-2])
yield s
def all_combos():
for a,b,c,d in itertools.product(range(71),range(61),range(91),range(11)):
if a+b+c+d == 100:
for p in terms(b,5):
for q in terms(c,5):
for r in terms(d,2):
yield [a]+p+q+r
对于解的数量。count_combos() 计算为 1470771090600747，大约是 1.5 万亿。请注意，这个函数需要 Python 3.8，因为它使用了最近添加的 math.comb.
实际使用发电机的全部内容是不可行的，但是，例如。
import random
some_combos = [list(c) for c in itertools.islice(all_combos(),1000000)]
for _ in range(5): print(random.choice(some_combos))
典型的输出：
[0, 0, 0, 0, 0, 2, 0, 13, 13, 32, 31, 8, 1]
[0, 0, 0, 0, 0, 2, 0, 5, 36, 28, 20, 6, 3]
[0, 0, 0, 0, 0, 2, 0, 8, 42, 16, 23, 4, 5]
[0, 0, 0, 0, 0, 2, 0, 13, 42, 12, 22, 1, 8]
[0, 0, 0, 0, 0, 2, 0, 10, 69, 7, 3, 8, 1]
在编辑时 在我第一次实现 count_combos 这是我固定的。除此以外，我将保持答案的原样。它指的是问题的早期版本，例如A组有71种可能性，而不是只有8种。这个答案强调了1%的增量会导致解的数量不可行。当我调整代码，使e.g.成为 "A "组的71种可能性，而不是只有8种。range(71) 变成了 range(8)，我在他们的回答中得到了和阿恩完全一样的计数。
根据新问题编辑的答案
你可以使用列表理解，它的速度相当快。下面的代码在我的电脑上只花了几秒钟。我使用了John Coleman的想法，首先找到每组和的可能组合。我还使用了整数而不是浮点数。要将解法转化回问题中所说的问题，将每个列表值除以10。
from itertools import product
A = range(8) # 1 value from this group
B = range(7) # 5 values from this group (with replacement)
C = range(10) # 5 values from this group (with replacement)
D = range(2) # 2 values from this group (with replacement)
# use John Coleman's idea:
# first find all possible combinations of sums per group
groupsums = [sums for sums in product(A, B, C, D) if sum(sums) == 10]
print(len(groupsums)) # -> 95
def picks(maxi, n):
"""Returns list of combinations of n integers <= maxi
that sum to maxi."""
return [combi for combi in product(range(maxi + 1), repeat=n)
if sum(combi) == maxi]
# make list of lists that each have 13 items from the above ranges,
# with constraints as stated in the question
samples = [[a, b0, b1, b2, b3, b4, c0, c1, c2, c3, c4, d0, d1]
for a, b, c, d in groupsums
for b0, b1, b2, b3, b4 in picks(b, 5)
for c0, c1, c2, c3, c4 in picks(c, 5)
for d0, d1 in picks(d, 2)]
# show the first 5 and last 5 results
for i in range(5):
print(samples[i])
print('...')
for i in range(1, 6):
print(samples[-i])
# show the number of solutions
print(len(samples))
95
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 7, 0, 1]
...
[7, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
313027