我有24个项目需要分成6组4.我可以使用什么算法来查找所有可能的组合?
我有24个独特的项目。
我需要将它们分成6组,每组由4个项目组成。
我可以使用什么算法来迭代考虑订单的这24个项目的所有可能组合/分离是不相关的
例如,一个这样的组合将是:
ABCD-EFGH-IJKL-MNOP-QRST-UVWX
^因为顺序不重要,所以这将是:
DCBA-HGFE-LKJI-POMN-TSRQ-XWVU
^但他们会有不同于:
渔护署-EBGH-IJKL-MNOP-QRST-UVWX
……这是一个独特的组合。
所以只是重申:我正在试图弄清楚如何从24个项目中获得所有可能的组合,考虑到我需要将它们分成6组,每组4个。
此外,6组的排序也不重要。 含义:“ABCD-EFGH-IJKL-MNOP-QRST-UVWX”与“EFGH-IJKL-MNOP-QRST-UVWX-ABCD”相同
注意:在Java中实现这一点的帮助会很棒。
谢谢!
编辑:
解决方案如何:
(1)我首先尝试找到所有可能的四个组,给出24个项目。 (2)然后我找到所有可能的六个组,给出由#1产生的组
思考?
这类问题的常见攻击角度是为每个要枚举的对象定义规范表示,然后使用修剪进行递归。 对于您的特定问题,让我们规定规范表示法按照排序顺序对每个组中的字母以及组本身进行排序。 使用递归,我们以所有可能的方式执行以下操作。 把A放在第一组。 将B放入第一组或第二组。 如果A和B在一起,则将C放在第一组或第二组中。 如果A和B分开,则将C放入第一,第二或第三组。 通常,将每个连续的字母放在一个组中,该组中已有字母或第一个空组。
python:
def combinations(unassigned, groupcountmax, groupsizemax, groups=()): if not unassigned: yield groups else: x, unassigned1 = unassigned[0], unassigned[1:] for i, group in enumerate(groups): if len(group) < groupsizemax: yield from combinations(unassigned1, groupcountmax, groupsizemax, groups[:i] + (group + x,) + groups[i+1:]) if len(groups) < groupcountmax: yield from combinations(unassigned1, groupcountmax, groupsizemax, groups + (x,))
将24个项目的划分计算为6个4个集合将需要相当长的时间,因为它们有24个!/(6!(4!)^ 6)~4.5e12。