Algorithm - Grouping List in unique pairs

Question

I'm having difficulties with an assignment I've received, and I am pretty sure the problem's text is flawed. I've translated it to this:

---

Consider a list x[1..2n] with elements from {1,2,..,m}, m < n. Propose and implement in Python an algorithm with a complexity of O(n) that groups the elements into pairs (pairs of (x[i],x[j]) with i < j) such as every element is present in a single pair. For each set of pairs, calculate the maximum sum of the pairs, then compare it with the rest of the sets. Return the set that has the minimum of those.

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)

---

The things that strike me oddly are as follows:

• Table contents definition It says that there are elements of 1..2n, from {1..m}, m < n. But if m < n, then there aren't enough elements to populate the list without duplicating some, which is not allowed. So then I would assume m >= 2n. Also, the example has n = 2 but uses elements that are greater than 1, so I assume that's what they meant.

• O(n) complexity? So is there a way to combine them in a single loop? I can't think of anything.

---

My Calculations:

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: ?

So obviously, I cannot use brute force and then figure out if it is valid after then. The formula I used to calculate the total possible ways is

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

---

Question:

Is this problem wrongly written and impossible to solve? If so, what conditions should be added or removed to make it feasible? If you are going to suggest some code in python, remember I cannot use any prebuilt functions of any kind. Thank you

Answer 1

Assuming a sorted list:

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

Or if you want to do it more manually:

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

Output:

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