Are there any algorithm that solves the following problem in time less than O(n!), like polynomial time? Otherwise, for this problem, does not anyone have found any polynomial time algorithm, like NP problems?

Input: n (number of elements)

Output: a list of all combinations of two, where, from top of the list, each unit of combinations of n/2 must have all elements.

Example 1

Input: n=4
Output: 
[0, 1], [2, 3],
[0, 2], [1, 3],
[0, 3], [1, 2]

Example 2

Input: n=8
Output: 
[0, 1], [2, 3], [4, 5], [6, 7],
[0, 2], [1, 3], [4, 6], [5, 7],
[0, 3], [1, 2], [4, 7], [5, 6],
[0, 4], [1, 5], [2, 6], [3, 7],
[0, 5], [1, 4], [2, 7], [3, 6],
[0, 6], [1, 7], [2, 4], [3, 5],
[0, 7], [1, 6], [2, 5], [3, 4]

P.S. The following answer does not meet the requirements. The first two (= n/2) pairs ([0, 1], [0, 2]) do not have "3", so the answer does not meet the condition where "0" and "1", "2", "3" must be in the first two pairs.

>>> n=4
>>> for i in range(0, n-1):
...   for j in range(i 1,n):
...     print( [i, j] )
...
[0, 1]
[0, 2]
[0, 3]
[1, 2]
[1, 3]
[2, 3]

CodePudding user response：

Yes, this problem can be solved in quadratic time. It is not too hard to explicitly construct these pairings.

It is quite helpful to consider a regular (n-1)-gon with one additional point in the middle. Then take the lines through one of the (n-1) endpoints and the midpoint and choose the pairs given by the symmetry of this line.

CodePudding user response：

As I said in my comment, this appears to be a type of (relaxed) Sports League Scheduling problem. If I understand what you are asking for, it can be summarized as follows:

Given a positive even integer N generate a set of n/2 "rounds" of pairings with the following qualities:

1. A pairing is a pair of two different integers [a, b] such that a and b are integers from 0..n-1 and a < b.
2. A round consists of n/2 pairings, such that every element from 0..n-1 appears exactly once in a pairing in the round, and
3. All pairings are unique across all rounds (that is no pairing ever appears more than once in the complete solution).

Assuming that this is a correct formulation of your problem, then the answer is

Yes, this can be done in O(n^2).

Further, not only can it be done, there exists a simple method to solve it for any even N:

For the first round, make n-1 pairs, filling in the first element of the pairs with the integers from 0 to (n/2)-1 going left-to-right. This how it would look for N=8:

[0, ], [1, ], [2, ], [3, ]

Then, fill in the second elements with (n/2) to n-1, but going right-to-left:

[0, 7], [1, 6], [2, 5], [3, 4]

This completes your first round.

For the next round, copy the first round, but keeping 0 in the same place, move the remaining left-side elements up the list, and the right-side elements down the list. When an element reaches the end of the list, reverse direction and swap them from first elements to second elements (or vice-versa):

    ----------------------->
[0, 7], [1, 6], [2, 5], [3, 4]
    <-----------------------

Becomes

    ----------------------->
[0, 6], [7, 5], [1, 4], [2, 3]
    <-----------------------

Now you just continue this process until you have N/2 rounds:

[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [7, 5], [1, 4], [2, 3]
[0, 5], [6, 4], [7, 3], [1, 2]
[0, 4], [5, 3], [6, 2], [7, 1]

Finally swap any pairings where the first element happens to be greater than the second:

[0, 7], [1, 6], [2, 5], [3, 4]
[0, 6], [5, 7], [1, 4], [2, 3]
[0, 5], [4, 6], [3, 7], [1, 2]
[0, 4], [3, 5], [2, 6], [1, 7]

If you check this solution you will find that it fulfills all of the constraints. This solutions works for any even value of N and obviously runs in O(n^2) time.