Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

• person 1 has item A, C, D, and wants item F

• person 2 has item B, C, and wants E

• person 3 has item E, and wants G

...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.

So my question would be:

1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
2. How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
3. What would be the complexity for finding longest/shortest paths?

• If you don't require the trades to form a single loop, then it sounds like you're looking for "math trades", look at Chris Okasaki's interesting write-up here and here (more algorithmic detail). Poly-time solvable and already implemented! :) OTOH if you do require a single loop, I can tell you right now that the problem is basically a generalisation of Hamiltonian Cycle and thus NP-complete. Oct 21, 2016 at 16:09
• all exchanges are one item for one item ? Oct 21, 2016 at 18:45
• Please do not post the same question on multiple Stack Exchange sites. You also posted this question on Software Engineering.SE (formerly Programmers.SE): softwareengineering.stackexchange.com/questions/334277/… Oct 21, 2016 at 20:25