Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$.
Now I'd like to order these sets in a list so adjacent sets are disjoint. This only works for $n > 4$.
Furthermore given a partially filled list, I want to be able to increase $n$ and therefore creating more pairs which need to be appended to the end of the list. The existing order of the list cannot be altered. If collisions can not be avoided, they need to be minimal.
e.g. the partial list
({1,2}, {3,4}, {5,1}, {3,2})
for $n = 5$ is given and $n$ is increased by 1:
({1,2}, {3,4}, {5,1}, {3,2}, {6,1}, {3,5}, {6,2}, {1,4}, ...)
Can this problem be solved in polynomial time?
I thought of the following greedy algorithm:
- pick the least used number that is not a subset of the previous set
- if there are multiple least used numbers, pick the one that has the highest distance to its last use