Given a machine that can sort 5 of your objects. How fast can we sort 25 of them?

Question

Assume that, you have 25 objects, and a machine that can sort 5 of them by some criteria that you don't even know. The cost of using this machine is very expensive (1$ for one launch), so what is the minimal cost of sorting all of your objects?

My current solution is very simple (similar idea to merge sort):

1. Randomly divide them into 5 groups of 5 objects
2. Sort each of them (+5 launches)
3. Now, sort the minimal elements of these five groups (+1 launch)
4. Now we have the minimal element of the whole set. Remove it from the group that it's belong to, and repeat the step 3 until only 5 unsorted objects left in general (+19 launch)
5. Sort the rest 5 objects (+1 launch)

So, in general, we have to pay 26$ (26 launches).

Question: Is there any way to make it cheaper (sort them in the least number of launches)?

Answer 1

Here is a greedy algorithm for choosing which objects to sort at each iteration:

Sorting 25 objects a_i is the same as completely filling a table M_25x25, where M_i,j = 1 if a_i > a_j, and –1 otherwise. After you perform a single iteration of sorting with the machine, you get immediate relations between the elements you have just sorted (up to 5 cells immediately filled), but after that you can fill more cells using commutativity (i.e. if a > b, then you know that b < a) and transitivity (i.e., if a > b and b > c, then you know that a > c).

To select 5 elements for the next sorting, you choose the elements, for which there are most empty cells in the intersections between rows and columns corresponding to those elements. For that you can just compare all possible combinations. There are 25 choose 5 = 53130 possible variants, and the complexity is actually exponential, but that doesn't cost any "money" in this problem.

When the table is completely filled, you can build the sorted sequence with Topological sort, or simply by sorting elements by the sum of the values in the the corresponding table row: the higher the sum, the larger the element.

This is not ideal, but quite effective. I've tested this method on random permutations and the result is about 16.8$ on average. Here is a code sample in Python:

import random
import itertools


class SortingMachine:
    def __init__(self):
        self.coins = 0

    def sort(self, elements):
        assert(len(elements) == 5)
        self.coins += 1
        return list(sorted(elements))


def test_sorting(seq):
    N = len(seq)
    machine = SortingMachine()
    table = [[0 if i == j else None for j in range(N)] for i in range(N)]

    # Fill empty table cells using transitivity with Floyd-Warshall algorithm
    def fill_transitive():
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if table[i][j] is None and table[i][k] == table[k][j]:
                        table[i][j] = table[i][k]

    # Register in the table the information that seq[i] > seq[j]
    def set_greater(i, j):
        table[i][j] = 1
        table[j][i] = -1

    # Register in the table information from 5 sorted elements
    def register_sorted(sub):
        for (el1, i1), (el2, i2) in zip(sub, sub[1:]):
            set_greater(i2, i1)

    # Select 5 elements to send to the machine
    def choose_elements():
        # Count empty cells in the cells corresponding to 5 comb elements
        def empty_cells(comb):
            return sum(table[i][j] is None 
                       for i, el1 in comb for j, el2 in comb)
        comb = max((empty_cells(comb), comb) 
                   for comb in itertools.combinations(enumerate(seq), 5))[1]
        return [(el, ind) for ind, el in comb]

    # Return True if the table is completely filled
    def is_complete():
        return all(all(el is not None for el in row) for row in table)

    while not is_complete():
        chosen = choose_elements()
        sorted_chosen = machine.sort(chosen)
        register_sorted(sorted_chosen)
        fill_transitive()

    # Checking that the sorting is correct
    sorted_seq = list(sorted(seq))
    assert(all(sorted_seq.index(seq[ind]) == (sum(row) + N - 1) // 2 
               for ind, row in enumerate(table)))

    return machine.coins


def random_sequence():
    l = list(range(25))
    random.shuffle(l)
    return l

The greedy heuristic in this method maximizes only the immediate information gained from the sort, without accounting for transitivity. Now, theoretically a better heuristic is to maximize the expected information the sorting of the 5 chosen elements gives, including all the information gained by transitivity. That is, choose 5 elements, with the maximum average (over all possible sorting outcomes of them) number of filled cells after considering transitivity. But the naive algorithm to implement that will take much longer to compute.