How to find chains of pairs?

Question

Programming

I got a task:
1. there is a person who has a 3-room apartment. He wants to sell it and buy 2 apartments for 1 room + take the money.
2. There is a person who just sells a 1-room apartment.
3. There is a person who sells a 2-room apartment
4. There is a person who simply sells a 1-room apartment, pays extra and buys a 2-room apartment.
And now you need to make a chain of all these people so that everyone participates in the deal and everyone is satisfied. The question is that there is a volume of buyers and sellers comparable to avito and a real estate agency that needs to spud (ideally) all people. Those. you need to make the shortest pairs, you can make chains of 3-4 buyers, as long as there is maximum coverage. A direct search will be incredibly long. What is the best way to solve this problem?

Answer 1

The shortest graphs and the maximum coverage are mutually exclusive things to me.

Answer 2

The task is similar to the clearing task, only with a wider set of conditions.
The task of clearing is when there is a situation:
A must B. B must C. C must A.
The task of clearing is to find such chains among the set of debts of agents and make the maximum netting between agents.
In general terms, your task is good for Prolog, but there it will drown by itself in combinatorial complexity and will not produce a result + a description of the rules is still something to do.

Answer 3

Most likely it is necessary for each requirement to choose to form an array of possible solutions and rank them according to different criteria. For example, air ticket sites do this by the number of transfers. There will be a similar algorithm.
If you do this all the time - yes, a resource-intensive task, but if, when a new proposal arrives, you make a miscalculation for it throughout the database, then it is quite normal.
At the moment when the client requests the chain, it is already there, there is no need to calculate it at this moment.

Answer 4

The picky bride problem

Answer 5

And another part of the clients will refuse a number of chains, so it is impossible to find one and only, and there will be a lot of options.
In any scenario, for each link in the chain there will be a number of criteria, satisfying which we get a certain set, as a result we apply combinatorics and get a lot of options in each case.