An order

The Cheapest Way to Rank a Field

Five comparisons can rank six candidates, and exactly seven hundred and twenty of the ninety-six thousand ways to make five comparisons do it — one for each order.

at most 96096 outcomes

Home · An order · Reference

Ranking six candidates takes at least five comparisons.

Fewer cannot do it: with four comparisons at most five candidates can be connected to each other at all, and two candidates with no path between them could go either way round.

The fewest comparisons that can rank the field

line with a head: a pair compared; the head points at whoever came out behind
no line: a pair nobody compared
closed ring of three: a circular triple: no order can hold all three

Three outcomes drawn. Rows differ in how many candidates. Which candidate is which is the drawing's own choice and carries no meaning. Teams comparing routes, outcomes and corrections can see what the platform records today, then check whether the resulting evidence improves the decision in practice.

Three, four and five comparisons on fields of four, five and six. In each row the number of outcomes that rank the field completely is the number of orders: twenty-four, one hundred and twenty, seven hundred and twenty. A separate technical or research perspective relevant to the comparison can be found at data.world.

Computed from the three numbers alone. Who the candidates are and what any comparison was about is outside the record; the counts are of outcomes, not of anybody.

The fewest, and what they have to be

A chain.

Compare the first with the second, the second with the third, and so on down the field. Five comparisons, each one linking a new candidate to the one before, and the order falls out of them directly.

Any other arrangement of five comparisons fails. Compare one candidate with all five others and the field is split into one placed candidate and five unplaced ones. Compare in two separate groups and the groups float free of each other.

How many of the possible outcomes do it

Seven hundred and twenty, out of ninety-six thousand and ninety-six.

That is the number of orders of six candidates, and the correspondence is exact: each order gives one chain and each chain gives one order. There is nothing to choose beyond which order it is.

Four candidates with three comparisons: twenty-four of one hundred and sixty. Five with four: one hundred and twenty of three thousand three hundred and sixty.

At the minimum number of comparisons, the outcomes that rank the field are exactly the orders, one each, and they are a vanishing part of what those comparisons could have produced.

The shares

Twenty-four in one hundred and sixty is three in twenty. One hundred and twenty in three thousand three hundred and sixty is one in twenty-eight. Seven hundred and twenty in ninety-six thousand and ninety-six is about one in a hundred and thirty-three.

So the minimum is a real minimum and a thin one. Spending exactly the fewest comparisons that could rank the field will rank it only if they are spent in one of the very few arrangements that work.

What goes wrong with the other outcomes

Mostly not contradiction.

Of the ninety-six thousand and ninety-six outcomes with five comparisons among six candidates, eighty-three thousand nine hundred and fifty-two contain no ring. Of those, seven hundred and twenty rank the field. The remaining eighty-three thousand two hundred and thirty-two are perfectly consistent and simply do not say enough.

Twelve thousand one hundred and forty-four outcomes do contain a ring, which is about one in eight. Contradiction is the smaller problem at this end of the table; silence is the larger one.

What the minimum looks like on smaller fields

Two candidates need one comparison, and that one comparison ranks them. Both of the two possible outcomes rank the field, so the share is one — the only page in the record where the minimum always works.

Three candidates need two comparisons. Twelve outcomes, six of which rank the field: a half.

Four need three: one hundred and sixty outcomes, twenty-four ranking, three in twenty.

Five need four: three thousand three hundred and sixty, one hundred and twenty, one in twenty-eight.

Six need five: ninety-six thousand and ninety-six, seven hundred and twenty, one in a hundred and thirty-three.

One, a half, three in twenty, one in twenty-eight, one in a hundred and thirty-three. The minimum stops being a realistic hope almost immediately.

Knowing the chain in advance

A chain only ranks the field if it is the right chain, and the right chain is the order — which is the thing being looked for.

So the minimum is available in hindsight and not in advance. A comparer who knew which five comparisons to make would already know the answer, and the fact that five comparisons suffice is a statement about the arithmetic rather than a method.

What is available in advance is the floor: five comparisons is the fewest that could possibly work for six candidates, so any plan involving four is a plan that cannot finish. That much is worth knowing before starting, and it costs one subtraction.

The floor is cheap to check and worth checking

Count the comparisons and compare with the field size less one.

That is the whole test, it takes a second, and it answers a question that is otherwise easy to get wrong: whether the comparing done so far could possibly have ranked the field. Below the floor the answer is no, whatever the results were.

It is the one piece of this record that can be applied in the middle of the work rather than before it or after.

Why the floor and the minimum are not the same claim

One is about connectedness, the other about agreement.

The floor says five comparisons are needed to connect six candidates: with four, some candidate sits apart from the rest and no arrangement of results can place them. That is a statement about which pairs were looked at, and it holds whatever the results were.

The minimum says that five comparisons sometimes do rank the field — seven hundred and twenty of the ninety-six thousand and ninety-six outcomes at that amount of comparing, about one in a hundred and thirty-three. That is a statement about results, and it requires the five comparisons to form a chain and the results along it to agree.

Confusing the two produces the belief that reaching the floor is most of the work. It is the first one per cent of it.

What the minimum is good for

Ruling things out.

It cannot say that a plan will work and it can say that a plan cannot. Four comparisons on six candidates will not rank them, whatever the results and whoever is comparing, and knowing that before starting is worth more than most of what this record offers.