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.
