Algorithm to find least number of trades between people

Admin 1
Viewed 131

I have been thinking about this question for a while now.

Let's say there is a list s that contains books that people are selling. I have a book in s, and I want to trade for a book that is in s (something I don't have).

Each person in this scenario is selling one book in s, and also wants one book that is in s.

Is there an algorithm to find out the least number of trades required between people to get the book that I want (and give my book to people who want it)?

Please tell me if this seems confusing (because it probably is).

Thanks for answering the question!

EDIT: List s can grow at any time.

algorithm java
2 Answers

EDIT: This answer assumes you want everyone to have their desired book at the end of the day. Other answer(s) address the case where all you care about is obtaining your desired book.

I believe this is equivalent to the minimum number of swaps to sort an array. Number the books 1 to N, and number the people 1 to N such that person i wants book i. Now we have an array like:

Book:    2  1  4  3
Person:  1  2  3  4

i.e. Person 1 has book 2, person 2 has book 1, etc. Now a trade is just a swap in this array, so we just want the minimum number of swaps to sort the array. This is a known problem.

If you can have more than one person selling a given book, or more than one person who wants a given book, you'd have to make sure that for each book, the number of people who want it equals the number of people selling it, otherwise there's no solution. Then, just use multiple copies of the book in the "book" array, again sorting people by the numeric value of the book they want. For example, let's say we have 4 people and 2 books, where two people want book 1 and two people want book 2; we'd have:

Book:    2  2  1  1
Person:  1  2  3  4

Again, we want to sort the "book" array in the fewest number of swaps.

user_13573410

I would turn this into a graph as follows. Books are the nodes of the graph. You have a directed edge from book A to book B if someone in S is offering book B and wants book A. You are looking for the shortest path from the book that you have to the book that you really want.

The shortest path can be discovered by a breadth-first search. You can implement one as follows:

todo = [starting_book]
path = {starting_book: None}
while len(todo) and target_book not in path:
    book = list.pop(0)
    for next_book in neighbors(book):
        if next_book not in path:
            path[next_book] = book
            todo.append(next_book)
if target_book in path:
    solution = [target_book]
    while solution[-1] != starting_book:
        solution.append(path[solution[-1]])
else:
    solution = None

Note, the solution that I am offering here gives the set of book trades to happen, but not the people. Turning a particular book trade back into the person to talk to can be done either by searching s or with a lookup table.

This is also not an online solution - keeping track of shortest paths as things are added to/removed from s is going to be a lot of work.

user_5854110
Related