Standard sorting is very much possible, and it is exactly what you should be doing here.
- the problem differs in that the ordering is unknown
There is no difference. A standard sorting algorithm does not know the "rank" or "strength" of any of the items it is sorting ahead of time. In fact, it never knows it. All it knows is that there is a way of asking "does item A come before or after item B?". Typically this is done by means of a function that is called multiple times during sorting.
Since the aim of most sorting algorithms to minimise the number of comparisons, and you want to minimise the number of comparisons, you have your answer there. Moreover, if you don't want to order all the items but (say) find the top ten, there are well-known sorting algorithms that will do this as well.
It is true that in most cases discussed in textbooks, it is possible to answer "does A come before or after item B?" purely algorithmically, using information stored within A and B. All the examples you tend to see will assume this. But this is not essential. There is nothing wrong with a comparison function whose implementation is:
- Present A and B to the user.
- Ask the user which should come first.
- Return the user's answer to the sorting algorithm.
and such an function is exactly what you would be using here.
- the problem differs in that the ordering… can differ between users
There is no difference here either. "Sorting according to Archibald's opinion" and "sorting according to Ermintrude's opinion" are two separate sorting operations, conducted separately on behalf of two separate users - just as "sorting according to weight" and "sorting according to height" are two separate sorting operations, conducted separately on two different sorting criteria.
I don't think it's possible to strictly satisfy this requirement in a round-robin system:
H/A rotation: each team should play a home game and an away game every
other round, i.e. in a tournament with 5 rounds, a given team should
have the following rotation: H-A-H-A-H.
Let's say you have a round-robin system where every team takes part in one match each round and every team has a perfectly alternating home-away-schedule. Let A and B be teams that both play at home in the first round. Then they'll be playing at home every odd round and playing away every even round. There will never be a round where A plays at home and B plays away or vice versa. Consequently, if A and B do not share the home location, then A and B will never face each other. The system is flawed.
I think assigning the team location (Home or Away) to the rows of the standard round robin algorithm and alternating them should work reasonably well.
So, for round one (and for each odd round) you would have home teams in the first row and away teams in the second row:
Round 1. (1 plays 14, 2 plays 13, ... )
1 2 3 4 5 6 7 (Home)
14 13 12 11 10 9 8 (Away)
For round two (and for each even round) you would have away teams in the first row and home teams in the second row:
Round 2. (1 plays 13, 14 plays 12, ... )
1 14 2 3 4 5 6 (Away)
13 12 11 10 9 8 7 (Home)
Alternating home and away could be implemented by taking the first algorithm and changing this line
pairings.append((teams[i], teams[len(teams) - i - 1]))
into something like this
if turn % 2:
home = teams[i]
away = teams[len(teams) - i - 1])
else:
home = teams[len(teams) - i - 1])
away = teams[i]
pairings.append((home, away))
Best Answer
As I can see you want to find maximum matching in graph. In fact nodes are players, they connected to each other if they aren't in same club, now you should find maximum number of edges which are doesn't have same vertex. See Edmonds Maximum matching algorithm.