Well it’s a problem me and my friend had thought of, and well, haven’t come up with anything to solve the following problem(I’ll try to phrase it in the best way I can):
Given that there are
nnumber of teams, and the number of matches each team has played, and that no team can play more than 2 matches with any other team, predict if the distribution of matches played by each team is possible.
P.S. : I am a Python Programmer, so (if possible) post only python code for explaining..
4
This is a nice exercise in constraint propagation and combinatorics. Here are some ideas:
- Clearly there are result distributions which are impossible. For instance, the total number of of wins must equals the total number of losses, and the total number of draws must be an even number.
- If you draw up some example distributions by adding up actual results, you will start noticing more regularities. Each of those is another criterion for proving that a given distribution is impossible.
- Showing that a distribution is possible is a little harder. The most direct proof is to give a concrete example of results which would result in the distribution you are given..
- If you can’t manage to construct one, the most straightforward algorithm to decide if there is one is to enumerate all possible pairings and see whether they fit. For instance, starting with the top-ranked team, you can conduct a complete search: have they won, lost, tied, or not yet played against the second-ranked team? (You said that there are return games, so this decision has to be made twice, but that doesn’t change the basic idea of a complete search.) Either you find a matching configuration of results, or you have proved that there isn’t one.
- A complete search is expensive, but there are various constraints that you can use to prune the search space. For instance, you cannot assume more wins for a team than the input said they have, and the assumption of how A played against B must confirm to what you assume about B vs. A.
1