I am currently looking to implement an algorithm, that matches a given set of individuals, and produces groups of three individuals who have all never seen each other. So far I have been trying to achieve this by creating an array and assigning each individual a prime number (the id), which gets multiplied with another individuals id to create a key upon matching. This will then be used in successive matches to eliminate the possibility of matching again. So far the groups have been formed by simply taking a list of individuals, starting from the first and then matching that indiviual with the first individuals in the list, whose id does not divide the key, and then removes that group. However this has sometimes led to groups of people being left over, so i wanted to ask whether there is an existing algorithm for this problem already?
Asked
Active
Viewed 94 times
1
-
2https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem – David Eisenstat Feb 06 '22 at 15:33
-
This is effectively the Sports League Scheduling problem, which is kind of a three dimensional 8-rooks problem. Check out the tags wiki, there is a lot more information on it, but in general (and depending on the extra constraints) it is a hard problem. – RBarryYoung Feb 06 '22 at 16:02
-
Oops, sorry. I rescind what I said above, because the elements all come from the same set (instead of two or three different sets) it is not really the Sports League Scheduling problem. you might be able to call it a related problem though. – RBarryYoung Feb 06 '22 at 16:17
-
What is the maximum set size that you consider? – Damien Feb 06 '22 at 16:32
-
The groups we are trying to create will be either three four or five (four and five only when neat three is not possible) and the set from which we will pick is of varying size, but definetely bigger than 30 – IronicOwl Feb 08 '22 at 14:48