Prevent repeat pairings with the last N people you matched with

[liddiard]

N = 3 is probably reasonable. If a pairing would be a duplicate of one of a person's last N pairings, exclude it as a possibility. See discussion and some potential algorithms on this StackOverflow thread: https://stackoverflow.com/questions/3046482/random-pairings-that-dont-repeat.

Considerations

• Handle situations where this would result no potential matches: Should we throw an error, or just log a warning and allow a duplicate match?
• How does this work across multiple pools? Are the last N matches we look at for exclusion specific to the current pool? (Probably shouldn't be.) There might be some other multi-pool considerations here I'm not thinking of.
• There doesn't seem to be a great algorithm to do this.
  • The ideal we're really striving for here is a complete graph where given enough pairing rounds, all "nodes" (people) will be connected without duplicates before starting to create duplicates as no other non-repeat pairings are available. This is complicated, though, by the fact that nodes in this graph are constantly appearing and disappearing by people joining/leaving the channel or by saying they're available or not. This approach is probably not realistic?
  • The naive "greedy algorithm" of iterating through people and pairing them with someone they haven't met in the last N pairings can fail to find a "solution" even if one exists. This is because a choice of pairing in one of the previous iterations of the loop could "use up" a person who was necessary to pair with someone else to prevent a repeat pairing. This comment backs up my intuition on that. This may just be a case of "don't let the perfect be the enemy of the good," but we still have to figure out how to handle these scenarios, or just accept that the algorithm is imperfect and still may result in duplicate pairings sometimes.
  • We can retry if we fail to find a solution, but then we're dealing with non-deterministic time complexity, which doesn't really sit right with me in a world of hard timeouts on web servers. I mean we can just terminate after X unsuccessful iterations but gross. 😅
  • We can generate a hash table of pairs from the last N rounds to speed up performance, but it doesn't address the greedy algorithm issue.
  • How common will repeat pairings be with completely random matches in a group of size N with M previous rounds? How common will repeat pairings be with an imperfect algorithm aimed at preventing repeat pairings? It'll probably be a lot better, but these are questions I have and I don't know enough about probability and combinatorics to answer lol.
  • Should pairings even be random? Maybe we should just create a hashed value for each person, sort the of participants array based on that, and linearly probe until we find the next "available" person in that ordering. This is going to end up being an n^2 algorithm but maybe that's fine. How would this algorithm handle people joining and leaving, available and not available, for each round though? This approach sounds kinda promising but I'd need to think about it some more.

[liddiard]

improved matching using greedy "set difference" algorithm in: c0a74d4eabdb9c950d844b350c3d229faf821a6e it's not "perfect," but it should be a huge improvement in reducing the probability for duplicate pairings