I'm not sure that what you need is Edmond's blossom algorithm. Maximum matching is a problem on undirected graphs. Your problem seems to involve a directed graph structure (A prefers B doesn't mean B prefers A).
Daniel Prager's solution involves randomization, so I think it's possible that the solution will not be optimal. If optimality is of concern, you might consider expressing constraints in your problem as an integer program. I'm not sure if Racket has any integer programming library. Using SMT solvers is also another possibility. On Monday, May 14, 2018 at 7:51:17 AM UTC-4, Jens Axel Søgaard wrote: > > Context: > > I have students A, B, C, ..., Z that needs to work in pairs for their exam. > Each student has made a wish list with 3 other students that they'd like > to work with. > I need to find the maximum possible pairing. > > I think - maybe - that the algorithm I need is Edmond's blossom algorithm. > > > Am I so lucky that someone has this in Racket? > > https://en.wikipedia.org/wiki/Blossom_algorithm > > http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf > > /Jens Axel > > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
