与约束的组合找到从低到高的重新分区

Question

我有一个项目，我需要找到可以解决以下问题的算法：

具有三个项目列表：

A = [1,2,3,4,5]
B = [1,2,3,4,5]
C = [1,2,3,4,5]

使用 python 我可以通过这行代码找到所有独特的组合：

allCombinations = list(set(product(A,B,C)))

但现在我需要从所有这些组合中得到，这些组合遵循相当线性的重新分配。

比如有125种独特的组合，现在我想要50种组合，其中A1 B1 C1出现的次数少于A2 B2 C2 ...（如果能近乎线性就完美了）

我不知道如何解决这种问题，如何才能select符合我的想法的最佳组合。

125个组合我都能得心应手，再多就太难了

谢谢

#编辑

我将在此处重新制作示例。

A=[1,2] 
B=[1,2] 
C=[1,2]

此列表中的组合是

(1,1,1) (1,2,1) (1,2,2) (1,1,2) (2,1,1) (2,1,2) (2,2,1) (2,2,2)

如果我需要select 3种组合，我会选择(2,2,2) (1,2,2) (2,2,1) 因为我想为A做1， B、C 列出 A、B、C 中少于 2 个。

目标是生产稀有度，A,B,C代表三个物品列表。使三个列表中的第一项比第二项更稀有。

我想为很多项目做这件事。

Answer 1

我认为你的问题有点不明确，所以你可以选择如何准确地衡量你的组合。

一种可能性是选择随机组合，但权重 i*j*k 归因于组合 [A[i],B[j],C[k]]。因此，例如，组合 [A2,B2,C2] 被选为组合 [A1,B1,C1].

的可能性要高 8 倍

我们可以使用random.sample进行权重抽样：https://docs.python.org/3/library/random.html#random.sample

Python 3.9:

import itertools  # product
import random     # sample

def sampleCombinations(A, B, C, k):
  allCombinations = list(itertools.product(enumerate(A), enumerate(B), enumerate(C)))
  weights = [(i+1) * (j+1) * (k+1) for (i,_), (j,_), (k,_) in allCombinations]
  sampled = random.sample(allCombinations, k, counts=weights)
  sampled_clean = [(x,y,z) for (_,x), (_,y), (_,z) in sampled]
  return sampled_clean

print(sampleCombinations(['A1','A2','A3','A4','A5'], ['B1','B2','B3','B4','B5'], ['C1','C2','C3','C4','C5'], 50))

print(sampleCombinations([1, 2], [1, 2], [1, 2], 3))

请注意使用 enumerate 获取计算权重所需的索引 i,j,k。然后我们不要忘记在返回组合之前删除 sampled_clean 中的索引。另请注意，权重计算为 (i+1)*(j+1)*(k+1) 而不是 i*j*k，因为所有内容都是 0 索引的，而不是 1 索引的。

注意：random.sample 的“counts”关键字参数是 python 3.9 中的新参数。在3.9版本之前，需要手动复制种群中的元素来模拟权重。

Python < 3.9:

import itertools  # product
import random     # sample

def sampleCombinations(A, B, C, k):
  allCombinations = list(itertools.product(enumerate(A), enumerate(B), enumerate(C)))
  weights = [(i+1) * (j+1) * (k+1) for (i,_), (j,_), (k,_) in allCombinations]
  weightedCombinations = [c for c,w in zip(allCombinations, weights) for _ in range(w)]
  sampled = random.sample(weightedCombinations, k)
  sampled_clean = [(x,y,z) for (_,x), (_,y), (_,z) in sampled]
  return sampled_clean

print(sampleCombinations(['A1','A2','A3','A4','A5'], ['B1','B2','B3','B4','B5'], ['C1','C2','C3','C4','C5'], 50))
# [('A3', 'B4', 'C2'), ('A4', 'B4', 'C5'), ('A2', 'B5', 'C5'), ('A4', 'B4', 'C4'), ('A3', 'B1', 'C4'), ('A4', 'B3', 'C3'), ('A4', 'B4', 'C2'), ('A5', 'B3', 'C4'), ('A2', 'B5', 'C3'), ('A5', 'B2', 'C2'), ('A5', 'B4', 'C3'), ('A4', 'B3', 'C1'), ('A3', 'B2', 'C5'), ('A2', 'B5', 'C5'), ('A4', 'B5', 'C5'), ('A5', 'B5', 'C5'), ('A3', 'B4', 'C5'), ('A3', 'B4', 'C5'), ('A5', 'B4', 'C2'), ('A2', 'B3', 'C1'), ('A2', 'B5', 'C2'), ('A3', 'B4', 'C4'), ('A4', 'B5', 'C1'), ('A3', 'B2', 'C2'), ('A4', 'B3', 'C5'), ('A2', 'B3', 'C3'), ('A3', 'B4', 'C1'), ('A5', 'B5', 'C4'), ('A3', 'B5', 'C5'), ('A3', 'B2', 'C5'), ('A5', 'B5', 'C3'), ('A5', 'B5', 'C3'), ('A3', 'B4', 'C4'), ('A4', 'B1', 'C1'), ('A3', 'B3', 'C4'), ('A4', 'B2', 'C5'), ('A5', 'B5', 'C5'), ('A4', 'B4', 'C3'), ('A1', 'B5', 'C3'), ('A4', 'B5', 'C3'), ('A4', 'B4', 'C2'), ('A5', 'B2', 'C2'), ('A5', 'B2', 'C5'), ('A4', 'B3', 'C5'), ('A4', 'B5', 'C1'), ('A4', 'B3', 'C5'), ('A5', 'B5', 'C5'), ('A3', 'B5', 'C3'), ('A5', 'B4', 'C5'), ('A3', 'B1', 'C4')]

print(sampleCombinations([1, 2], [1, 2], [1, 2], 3))
# [(2, 2, 2), (2, 2, 2), (1, 1, 1)]

与约束的组合找到从低到高的重新分区

Combinations with constraints find a repartitions that goes from low to high

python

algorithm

combinations

generator

dynamically-generated