I am building a small web app that allow stamp collectors to swap their stamps. The main problem I am trying to solve is 1-on-1 (direct) swap. Since usually A needs something from B, but B not always need something from A.
But the solution is to find a circular swap, for example:
A needs from B
B needs from C
C needs from A
result: everyone is happy.
I have a list of collectors, and for each a list of stamps they got, and a list of stamp they are looking for.
I am trying to find a way, to create a circle, by matching the "have" and "want". The problem is that this may take a very long time with lots of collectors and lots of stamps .
What would be the best approach for this?
The straight forward algorithm I think (which is obviously not optimized) is to:
1) look what "B" want.
2) find who got what B want (stamp after stamp)
3) for each one, see if he (C) needs something from A
4) if yes, YAY
5) if not, see what C want (stamp after stamp)
6) for each one, see if (D) has something from A
... and so on ...
Any suggestions will be very welcome. Thank you