I have 24 items that I need to separate into 6 set

2020-07-27 04:30发布

问题:

I have 24 unique items.

I need to separate them into 6 groups comprised of 4 items each.

What algorithm can I use to iterate over all possible combinations / separations of these 24 items considering order is not relevant

For example, one such combination would be:

ABCD-EFGH-IJKL-MNOP-QRST-UVWX

^ Because order is not important, this would be the same as:

DCBA-HGFE-LKJI-POMN-TSRQ-XWVU

^ But they would be different from:

AFCD-EBGH-IJKL-MNOP-QRST-UVWX

...which is a unique combination.

So just to reiterate: I'm trying to figure out how to get all possible combinations out of 24 items considering I need to separate them into 6 groups of 4.

Also, the ordering of the 6 groups is also not important. Meaning: "ABCD-EFGH-IJKL-MNOP-QRST-UVWX" is the same as "EFGH-IJKL-MNOP-QRST-UVWX-ABCD"

NOTE: Help for implementing this in Java would be great.

Thanks!

EDIT:

What about a solution where:

(1) I first try to find all possible groups of four given the 24 items. (2) Then I find all possible groups of six given the groups yielded by #1

Thoughts?

回答1:

A common angle of attack for this kind of problem is to define a canonical presentation for each object to be enumerated and then use recursion with pruning. For your particular problem, let's stipulate that the canonical presentation has the letters in each group sorted as well as the groups themselves in sorted order. Using recursion, we do the following in all possible ways. Put A in the first group. Put B in the first or second group. If A and B are together, put C in the first or second group. If A and B are apart, put C in the first, second, or third group. In general, put each successive letter in a group with letters already in it or in the first empty group.

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,))

It will take quite a while to enumerate divisions of 24 items into 6 sets of 4, since there are 24!/(6! (4!)^6) ~ 4.5e12 of them.