Split array to sub-arrays 5 times while keeping unique pairs in all sub-arrays

Question

Background: I'm a conference manager and during the meetings I need to split the participates a few times into groups. I though to use python but I'm struggling.

I need to split 70 people into 10 groups of 7. Also, I need to split them 5 times (5 rounds). In each round I need that in each team, there won't be a pair that was together in the same team in all the rounds before that.

Let's say the people are an array [0,1,...,69] and splitting to groups is actually creating sub-arrays in equal size of 7.

A good output would be (example for 2 completely unique rounds and missing 3 rounds):

Round 1:
[[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13], [14, 15, 16, 17, 18, 19, 20], [21, 22, 23, 24, 25, 26, 27], [28, 29, 30, 31, 32, 33, 34], [35, 36, 37, 38, 39, 40, 41], [42, 43, 44, 45, 46, 47, 48], [49, 50, 51, 52, 53, 54, 55], [56, 57, 58, 59, 60, 61, 62], [63, 64, 65, 66, 67, 68, 69]]

Round 2:
[[0, 9, 18, 27, 35, 44, 53, 62], [1, 10, 19, 36, 45, 54], [2, 11, 20, 28, 37, 46, 55, 63], [3, 12, 29, 38, 47, 64], [4, 13, 21, 30, 39, 48, 56, 65], [5, 22, 31, 40, 57, 66], [6, 14, 23, 32, 41, 49, 58, 67], [15, 24, 33, 50, 59, 68], [7, 16, 25, 34, 42, 51, 60, 69], [8, 17, 26, 43, 52, 61]]

Round 3:
...

Round 4:
...

Round 5:
...

Any help please? I though this would be an easy task in python but I can't get it right for hours now. I would appreciate python code but any other language that I can easily compile and run it great too.

Many thanks.

Answer 1

This same approach runs much faster in Rust - full project files and binaries available here.

By the way, this problem is known by a lot of different names, one is the "Social Golf Problem". The original problem was published in some esoteric periodical from 1850, and called "Kirkland's Schoolgirl Problem". Combinatorics is an interesting domain of problems.

I've played around some more with a solution to this interesting problem, and came back to update this post. The code below is the primary piece of code that does groupings.

The participant objects each maintain a list of their 'acquaintances' which helps determine if they can join a group or not, among other things. The program can solve the problem anywhere from instantly to a minute or two. On average, it's just under 5 seconds (I have an old system). Running it on Pypy3 it's much faster.

This piece of code creates groupings for one round. It gets called 5 (or whatever the parameters specify) times per conference attempt.

def run_round(round_id, participants, groups):
    RAND_CANDIDATE_BIAS  = 4
    num_regroup_attempts = len(participants) * 2
    num_rand_candidates  = groups[0].size

    for participant in participants:
        found = False
        random.shuffle(groups)

        # First attempt to find a group.
        for group in groups:
            if try_join(participant, group):
                found = True
                break

        # If not successful, see if getting other participants (regroup 
        # candidates) to change groups will create an opening for the 
        # participant.
        if not found:
            for _ in range(num_regroup_attempts):
                if not random.randint(0, RAND_CANDIDATE_BIAS):
                    # Grouped acquaintances will try to regroup.
                    acqs       = participant.acquaintances
                    candidates = [a for a in acqs if a.group]
                else:
                    # Randomly selected participants will try to regroup.
                    candidates = random.choices(participants,
                                                k=num_rand_candidates)
                    candidates = [cand for cand in candidates if cand.group]

                random.shuffle(candidates)

                for regroup_candidate in candidates:
                    if change_group(regroup_candidate, groups):

                        # Candidate regrouped, see if there's an opening now.
                        if try_join_any(participant, groups):
                            found = True
                            break
                if found:
                    break

    return mixer.Round(round_id, groups)

Below is the output from the program. The first number of each row is the group number - it can be ignored.

Oo>>>>>> Sun Mar  8 20:53:12 2020 <<<<<<oO

Iteration 1 best so far: 1 groupless

[[[ Iteration 2 -- SOLVED!! ]]]

Conference(3,
    Round(1, [
        Group( 1, [ 1, 35, 41, 42, 44, 45, 57]),
        Group( 2, [ 2, 10, 37, 40, 43, 47, 55]),
        Group( 3, [ 3, 15, 31, 36, 62, 63, 68]),
        Group( 4, [ 4,  8, 20, 26, 29, 32, 54]),
        Group( 5, [ 5, 46, 64, 65, 66, 67, 69]),
        Group( 6, [ 6, 17, 22, 23, 27, 39, 53]),
        Group( 7, [ 7, 14, 21, 33, 48, 52, 60]),
        Group( 8, [ 9, 12, 25, 38, 49, 50, 70]),
        Group( 9, [11, 18, 19, 24, 34, 51, 59]),
        Group(10, [13, 16, 28, 30, 56, 58, 61]),
    ]),
    Round(2, [
        Group( 1, [ 1,  5, 10, 15, 51, 52, 70]),
        Group( 2, [ 2, 11, 25, 44, 46, 61, 68]),
        Group( 3, [ 3,  8, 12, 27, 34, 43, 67]),
        Group( 4, [ 4, 39, 41, 48, 55, 58, 65]),
        Group( 5, [ 6, 26, 28, 50, 59, 63, 64]),
        Group( 6, [ 7, 23, 36, 38, 45, 56, 66]),
        Group( 7, [ 9, 14, 16, 20, 22, 37, 42]),
        Group( 8, [13, 18, 33, 35, 54, 62, 69]),
        Group( 9, [17, 21, 24, 29, 31, 47, 49]),
        Group(10, [19, 30, 32, 40, 53, 57, 60]),
    ]),
    Round(3, [
        Group( 1, [ 1, 18, 27, 32, 37, 56, 68]),
        Group( 2, [ 2, 30, 45, 48, 50, 51, 67]),
        Group( 3, [ 3,  5,  6, 29, 38, 44, 60]),
        Group( 4, [ 4,  9, 23, 24, 40, 46, 62]),
        Group( 5, [ 7, 13, 22, 49, 55, 57, 63]),
        Group( 6, [ 8, 10, 25, 31, 33, 41, 59]),
        Group( 7, [11, 12, 15, 20, 35, 58, 66]),
        Group( 8, [14, 17, 19, 54, 61, 64, 70]),
        Group( 9, [16, 21, 26, 36, 43, 53, 65]),
        Group(10, [28, 34, 39, 42, 47, 52, 69]),
    ]),
    Round(4, [
        Group( 1, [ 1, 14, 31, 34, 46, 50, 58]),
        Group( 2, [ 2,  4,  6, 18, 21, 57, 66]),
        Group( 3, [ 3, 23, 26, 51, 55, 61, 69]),
        Group( 4, [ 5,  9, 13, 17, 32, 36, 59]),
        Group( 5, [ 7, 15, 37, 41, 53, 54, 67]),
        Group( 6, [ 8, 11, 40, 42, 56, 65, 70]),
        Group( 7, [10, 20, 27, 28, 49, 60, 62]),
        Group( 8, [12, 24, 30, 33, 39, 44, 63]),
        Group( 9, [16, 19, 35, 38, 47, 48, 68]),
        Group(10, [22, 25, 29, 43, 45, 52, 64]),
    ]),
    Round(5, [
        Group( 1, [ 1, 39, 43, 59, 61, 62, 66]),
        Group( 2, [ 2, 24, 38, 42, 53, 58, 64]),
        Group( 3, [ 3, 11, 16, 32, 33, 45, 49]),
        Group( 4, [ 4, 22, 31, 35, 60, 67, 70]),
        Group( 5, [ 5, 18, 20, 23, 41, 47, 63]),
        Group( 6, [ 6, 30, 36, 46, 52, 54, 55]),
        Group( 7, [ 7, 12, 17, 28, 51, 65, 68]),
        Group( 8, [ 8, 19, 21, 37, 44, 50, 69]),
        Group( 9, [ 9, 10, 29, 34, 48, 56, 57]),
        Group(10, [13, 14, 15, 25, 26, 27, 40]),
    ]))

Oo>>>>>> Sun Mar  8 20:53:13 2020 <<<<<<oO

There are more ways that this approach can be improved on. For instance, it could go back in time to earlier rounds and do participant group swaps to influence future/current openings for ungrouped members. Plus, a better algorithm for selecting regroup candidates and which groups they should swap to would be nice. Right now it's just random; based mostly on hunches.

Applied to the Kirkman's Schoolgirls problem.

Oo>>>>>>>>>>>>> Mon Mar  9 02:13:33 2020 <<<<<<<<<<<<<oO

Iteration 1 best so far: 7 groupless
Iteration 12 best so far: 6 groupless
Iteration 96 best so far: 5 groupless
Iteration 420 best so far: 4 groupless

[[[ Iteration 824 -- SOLVED!! ]]]

Conference(825,
    Round(1, [
        Group( 1, [ 1,  5, 15]),
        Group( 2, [ 2, 10, 14]),
        Group( 3, [ 3,  4,  8]),
        Group( 4, [ 6,  9, 13]),
        Group( 5, [ 7, 11, 12]),
    ]),
    Round(2, [
        Group( 1, [ 1, 11, 14]),
        Group( 2, [ 2,  4, 15]),
        Group( 3, [ 3, 12, 13]),
        Group( 4, [ 5,  6, 10]),
        Group( 5, [ 7,  8,  9]),
    ]),
    Round(3, [
        Group( 1, [ 1,  8, 13]),
        Group( 2, [ 2,  3, 11]),
        Group( 3, [ 4,  9, 10]),
        Group( 4, [ 5, 12, 14]),
        Group( 5, [ 6,  7, 15]),
    ]),
    Round(4, [
        Group( 1, [ 1,  7, 10]),
        Group( 2, [ 2,  6, 12]),
        Group( 3, [ 3,  9, 14]),
        Group( 4, [ 4,  5, 13]),
        Group( 5, [ 8, 11, 15]),
    ]),
    Round(5, [
        Group( 1, [ 1,  2,  9]),
        Group( 2, [ 3,  5,  7]),
        Group( 3, [ 4,  6, 11]),
        Group( 4, [ 8, 10, 12]),
        Group( 5, [13, 14, 15]),
    ]),
    Round(6, [
        Group( 1, [ 1,  4, 12]),
        Group( 2, [ 2,  7, 13]),
        Group( 3, [ 3, 10, 15]),
        Group( 4, [ 5,  9, 11]),
        Group( 5, [ 6,  8, 14]),
    ]),
    Round(7, [
        Group( 1, [ 1,  3,  6]),
        Group( 2, [ 2,  5,  8]),
        Group( 3, [ 4,  7, 14]),
        Group( 4, [ 9, 12, 15]),
        Group( 5, [10, 11, 13]),
    ]))

Oo>>>>>>>>>>>>> Mon Mar  9 02:13:38 2020 <<<<<<<<<<<<<oO

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

^^ Was the original combinatorics problem from 1850.

I find it interesting that solutions to that problem from 1850 focused on correlations to geometry to find possible groups.

The idea to go back in time to previous groupings and adjust them to make present groupings easier is something I did explore. It turned out to be simpler than the original description of the feature as I worded it. Moving participants around in previous rounds utilizes the exact same features used in placing participants in the current round; there aren't any "temporal" aspects of it. The rounds collectively are all part of one single larger grid.