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.

Reply via email to