# Stamps circular trade

Hi,

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 Â© needs something from Aâ€™s stamps collection
4. if yes, YAY
5. if not, see what C want (stamp after stamp)
6. for each one, see if (D) has something he wants from Aâ€™s stamps collection
â€¦ and so on â€¦

long procedureâ€¦

Any suggestions will be very welcome. Thank you

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).

1. A checks SOB against their â€śwantsâ€ť in CSO
2. This says B owns one of the ones they want.
3. B checks SOB against their â€śwantsâ€ť in CSO
4. This says C owns one of the ones they want
5. etc.
6. If a circle cannot be completed in a sensible n jumps, exit (to prevent infinite loops)
7. 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):

AFAIK the most popular:

2 Likes

Wow! I feel you gave me the right direction I was needed. Iâ€™m heading into this.
Thank you so much for the informative answer.