3

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?

Any advice would be appreciated.

  • recommended reading: Open letter to students with homework problems "...If your question on Programmers.SE is just a copy paste of homework problem, expect it to be downvoted, closed, and deleted - potentially in quite short order." – gnat Oct 21 '16 at 15:16
  • 1
    lol thanks for the remind but it's not a homework. It just occurred to me and I am interested in solving this but don't have a good idea how – Shuai Oct 21 '16 at 15:20
  • Are we assuming that a person is always willing to trade any one item they have for any one item they want? – Tanner Swett Oct 21 '16 at 18:07
  • This problem appears to be NP-Complete since it is a generalization of the Hamiltonian Circuit problem. So the complexity is exponential. – kevin cline Oct 21 '16 at 19:14
  • 2
    Please do not post the same question on multiple SE sites. You also posted this question on CS.SE: cs.stackexchange.com/questions/64922/… – wythagoras Oct 21 '16 at 20:26
3

Instead of a sparse matrix I'd go with a Directed Graph, where each node is a person and each link is a potential transaction.

Each cycle in the graph is a potential trade. See Best algorithm for detecting cycles in a directed graph for more information.

  • I thought about graph and you are right, if we have an arrow from p1 (person 1) to p2, that means p1 has an item to offer to p2. I am just thinking if it's possible to also record what those items are in the graph directly, or have another data structure to store those so when we find a cycle, we can immediately retrieve items involved for each person – Shuai Oct 21 '16 at 15:59
  • 2
    A directed link from p1 to p2 says that p1 has a product that p2 wants. It would be easy enough to record the name or ID of that product along with the link. – Dan Pichelman Oct 21 '16 at 16:02
2

I think a good way to represent the problem is as a bipartite, directed graph.

To create the graph, do this:

  • Draw a node for each person.
  • Also draw a node for each item.
  • Whenever a person has an item, draw an arrow from that person to that item. (The idea is: if the person is happy, then we can obtain the item.)
  • Whenever a person wants an item, draw an arrow from that item to that person. (The idea is: if we have the item, then we can make the person happy.)

Your goal is simply to find a circuit in this graph.

This means that your question can be rephrased as, "How can I find circuits in a bipartite directed graph?" The algorithms described in these questions and answers may be helpful:

(The difference between a circuit and a cycle is that a circuit can visit the same node multiple times (although it can't use the same arrow multiple times), while a cycle can only visit each node once. In the context of your problem, a cycle would mean that each person only participates in one trade, and each item only participates in one trade.)

-1

Edit: My other answer is better than this one; look at that one instead.

The problem can be represented by making a grid filled with dots. The grid has:

  • N rows, one for each person.
  • M columns, one for each item.
  • One green dot whenever a person is willing to give an item (because "give" starts with "G" for "green"). For example, if Bob is willing to trade up to three apples, then put 3 green dots in the grid cell which is in the row representing Bob and the column representing apples.
  • One red dot whenever a person wants to receive an item.

(In mathematical terms, this would be two N × M matrices, called G and R.)

Here's one algorithm for solving your problem. It's probably not the best algorithm, but it's an algorithm.

First, transform the grid into a directed graph by taking these two steps:

  • Draw an arrow from every green dot to every red dot in the same column (indicating that one person can give an item and another person can receive it).
  • Draw an arrow from every red dot to every green dot in the same row (indicating that a person can receive one item and give another item).

Second, find a directed cycle in the graph. This cycle provides the answer.

As an example, suppose that Bob has an apple and wants an orange, and Sarah has an orange and wants an apple. The grid would contain

  • a green dot for (Bob, apple),
  • a green dot for (Sarah, orange),
  • a red dot for (Bob, orange), and
  • a red dot for (Sarah, apple).

The cycle that we find

  • starts at the green dot (Bob, apple) and goes to the red dot (Sarah, apple) (Bob gives an apple and Sarah receives it);
  • goes from the red dot (Sarah, apple) to the green dot (Sarah, orange) (since Sarah received an apple, she's willing to give an orange);
  • goes from the green dot (Sarah, orange) to the red dot (Bob, orange) (Sarah gives an orange to Bob); and
  • returns from the red dot (Bob, orange) back to the green dot (Bob, apple) (Bob received an orange and so he's willing to give up an apple).
  • The problem with this algorithm is that if a person has 20 items they have and 50 items they want, that needs to be represented by 1,000 arrows. The same happens if an item is possessed by 20 people and wanted by 50 people. It would probably be more efficient to make use of the matrices G and R somehow, but I don't know how. – Tanner Swett Oct 21 '16 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.