algorithm - 给定一台可以对 5 个对象进行分类的机器。我们能以多快的速度对其中的 25 个进行排序？

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?

我目前的解决方案非常简单(类似于 merge sort 的想法):

1. 将它们随机分成 5 组，每组 5 个对象
2. 对它们中的每一个进行排序(+5 次启动)
3. 现在，对这五个组的最小元素进行排序(+1 启动)
4. 现在我们有了整个集合中的最小元素。从它所属的组中删除它，并重复步骤3，直到一般只剩下 5 个未排序的对象(+19 启动)
5. 对其余 5 个对象进行排序(+1 次启动)

因此，一般来说，我们必须支付 26$(26 次发射)。

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

Answer 1

这是一个贪心算法，用于在每次迭代中选择对哪些对象进行排序:

对 25 个对象 a_i 进行排序与​​完全填充表格 M_25x25 相同，其中 M_i,j = 1 如果 a< sub>i> a_j，否则为 –1。在使用机器执行单次排序迭代后，您会在刚刚排序的元素之间获得直接关系(立即填充最多 5 个单元格)，但之后您可以使用交换性填充更多单元格(即如果 a > b，则你知道 b < a) 和传递性(即，如果 a > b 和 b > c，那么你知道 a > c)。

要选择 5 个元素进行下一次排序，您可以选择这些元素对应的行和列之间的交叉点中空单元格最多的元素。为此，您可以比较所有可能的组合。有 25 种 choose 5 = 53130 种可能的变体，复杂度实际上是指数级的，但这在这个问题上并不花费任何“钱”。

当表完全填满后，您可以使用 Topological sort 构建排序序列，或者简单地按相应表行中值的总和对元素进行排序:总和越高，元素越大。

这并不理想，但非常有效。我已经在随机排列上测试了这种方法，结果平均约为 16.8 美元。这是 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

此方法中的贪婪启发式算法仅最大化从排序中获得的即时信息，而不考虑传递性。现在，理论上更好的启发式方法是最大化 5 个所选元素的排序所提供的预期信息，包括通过传递性获得的所有信息。即选择 5 个元素，在考虑传递性后，具有最大平均(在它们所有可能的排序结果中)填充单元格的数量。但实现该算法的朴素算法将需要更长的计算时间。