算法 - 以唯一对的形式对列表进行分组

Question

我在处理收到的作业时遇到困难，而且我很确定问题的文本有缺陷。我已将其翻译为：

考虑一个列表 x[1..2n]，其元素来自 {1,2,..,m}，m < n。在 Python 中提出并实现一个复杂度为 O(n) 的算法，该算法将元素分组成对（(x[i],x[j]) 对，其中 i < j），例如每个元素都存在在一对。对于每组对，计算对的最大总和，然后将其与其余组进行比较。 Return 具有最小值的集合。

For example, x = [1,5,9,3] can be paired in three ways:
(1,5),(9,3) => Sums: 6, 12 => Maximum 12
(1,9),(5,3) => Sums: 10, 8 => Maximum 10
(1,3),(5,9) => Sums: 4, 14 => Maximum 14
                              ----------
                              Minimum 10
Solution to be returned: (1,9),(5,3)

让我感到奇怪的事情如下：

Table内容定义表示有1..2n, from {1..m}, m < n的元素。但是如果 m < n，则没有足够的元素来填充列表而不复制一些元素，这是不允许的。那么我会假设m >= 2n。此外，该示例具有 n = 2 但使用大于 1 的元素，因此我认为这就是它们的意思。
O(n) 复杂度？ 那么有没有办法将它们组合在一个循环中？想不出来了

我的计算：

For n = 4:
Number of ways to combine: 6
Valid ways: 3

For n = 6
Number of ways to combine: 910
Valid ways: 15

For n = 8
Number of ways to combine: >30 000
Valid ways: ?

很明显，我不能使用蛮力，然后再判断它是否有效。我用来计算所有可能方式的公式是

C(C(n,2),n/2)

问题：

这个问题是不是写错了，无法解决？如果是这样，应该添加或删除哪些条件以使其可行？如果您打算在 python 中建议一些代码，请记住 我不能使用任何类型的任何预建函数 。谢谢

Answer 1

假设一个排序列表：

def answer(L):
    return list(zip(L[:len(L)//2], L[len(L)//2:][::-1]))

或者，如果您想更手动地进行操作：

def answer(L):
    answer = []
    for i in range(len(L)//2):
        answer.append((L[i], L[len(L)-i-1)]))
    return answer

输出：

In [3]: answer([1,3,5,9])
Out[3]: [(1, 9), (3, 5)]

算法 - 以唯一对的形式对列表进行分组

Algorithm - Grouping List in unique pairs

python

algorithm

combinatorics

minmax

code-complexity