选择平衡的组合子集

2024-05-15 03:55:49 发布

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

我有一个包含N个元素的数组。我想选择它们的M K组合,使元素尽可能均匀分布(即所有N个元素都有相同的次数,并且尽可能均匀地相互配对(或三倍,或等)。

例如,这是一个很简单的方法,或者至少足够简单,如果需要时间,可以手工处理以下值:

N = 8  
M = 14  
K = 4 

在14*4个可能的点,8个元素中的每个将出现14*4/8=7次。此外,每个元素将有7*(4-1)=21'合作伙伴',这意味着其他7个元素中的每个元素将显示21/7=3次。同样,由于每对出现三次,这些集合中还有3*(4-2)=6个点,这些点完全用其他6个元素填充。因此,每个元素出现7次,每对三次,每个三胞胎都是唯一的,所有三胞胎都存在。在关于如何开始构建这个集合的一些任意决定下,我大概花了十分钟来填写。

我想知道的是,对于一般情况,是否有这样的方法(最好是在Python中),或者至少有一个组合稍微不那么完美的情况,例如我现在正在研究的案例:

^{pr2}$

以前的一些逻辑仍然有效。每个元素出现22*6/12=11次,每个元素有11*(6-1)=55个伙伴,因此其他11个元素中的每个元素对它5次。在这五个配对中,还有5*(6-2)=20个点,其余10个元素每填充两次。因此,每个元素出现11次,每对5次,每三个三重集两次。不幸的是,向上一步移动并不奏效,因为三胞胎有2*(6-3)=6个空空间,将用剩下的9个元素填充,所以虽然四驱应该是唯一的,但它们并不都存在。

我已经尝试过用数学方法来处理这个问题,正如您所看到的,但是我希望有一种方法可以让Python为我做重提升(和随机化)。有什么想法吗?


Tags: 方法元素时间空间情况合作伙伴数组逻辑

热门问题