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:
This is really interesting, it’s a hard problem. The number of stamps I guess could be very large, so this is relatively difficult to optimist AFAICS – the number of permutations grows very quickly as the number of stamps and collectors grows. But if you’re not already aware of this, with your problem, you are describing a directed graph.
So my first thought had been two lookup tables. One with stamps -> owned by (table SOB). Then also the inverse, each collector maintains a list of owned/wanted, so collector -> stamps owned by/wanted (table CSO).
A checks SOB against their “wants” in CSO
This says B owns one of the ones they want.
B checks SOB against their “wants” in CSO
This says C owns one of the ones they want
etc.
If a circle cannot be completed in a sensible n jumps, exit (to prevent infinite loops)
If a circle can be completed record that as a possible trade sequence
But the issue is that there can be a lot of matches here. Assuming a large number of stamps, even a small amount of collectors could generate a huge number of variations here (which may not be an issue! databases are plenty fast).
And the second thing that’s I didn’t really notice until I’d though about the above is that this is a cyclic directed graph. So the graph nodes are collectors, who have owned/want lists (properties), and you connect the nodes from want --> owned (edges). Then you for any given collector you can a. tell who they want to connect to and then b. just walk from node to node – if you can walk from a given collector back to a given collector then that’s a cycle and that’s your chain. You still need to put measures in place to prevent endless cycles, and I guess you always want the shortest cycle as well, but they’re more implenetation details.
To solve this problem, I would strongly suggest looking at explicitly using a graph structure. I think it’s the only way you can keep this sane. What I’ve written above is just jottings really, it needs more though about how it’s structured, but it makes sense to me. So
Reasonable very high level overview of how you can write a graph structure, which I think gives a bit of an insight into how it works (Python):
Cycles are what you’re looking for, this was first thing I pulled up on cycle detection:
If you’re not at all familiar, you’ll need to do a bit of Googling. But finally, for databases that explicitly work as graphs (you can also create one using a relational DB & [if I remember correctly] a minimum of three lookup tables):