An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements

Question

Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates). For example, $$\begin{array}{l} T_0^4 = (0,1,2,3),\\ T_1^4 = (0,1,3,2),\\ \ldots \\ T_{23}^4 = (3,2,1,0). \end{array}$$

Assuming that $(x, y)$ are two different elements of a given tuple $T$, let $d(T, x, y)$ denote the number of elements between $x$ and $y$ in $T$. For example, if $T = (3, 0, 1, 4, 2)$, we have $$d(T, 3, 0) = d(T, 1, 0) = d(T, 2, 4) = d(T, 4, 2) = 0, d(T, 3, 2) = 3.$$

Question: given an arbitrary natural number $n > 2$ and a natural number $k$ such that $0 \leq k \le n - 3$, is there an efficient algorithm to generate a set $$S = \{T_{j_0}^n, T_{j_1}^n, \ldots, T_{j_m}^n\}$$ of tuples such that for any pair $(x, y)$ of elements of the set $\{0, 1, \ldots, n-2, n-1\}$ there exists an element $T_{j_z}^n$ of $S$ such that $d(T_{j_z}^n, x, y) \leq k$, yet the cardinality of $S$ is as small as possible?

The algorithm is expected to operate as follows: start with $T_0^n$; permute $T_0^n$ to obtain $T_{j_0}^n$; permute $T_{j_0}^n$ to obtain $T_{j_1}^n$, etc. (to avoid storing a large number of tuples in memory).

Answer 1

I will solve the case $k=0$ because it is in some sense also a solution to all other $k>0$. Since in each tuple only $n-1$ pairs of elements are adjacent, you need at least $\frac{n(n-1)/2}{n-1} = \frac{n}{2}$ tuples.

There is a nice and simple divide-and-conquer algorithm that can solve the question for $k=0$ close to optimally, in some sense. The idea is: divide the numbers in two sets. Solve the problem for both sets (recursively), that is: make a collection of partial tuples in which all numbers are adjacent in some tuple. Then we only need to guarantee the adjacencies between the two sets. This can be solved by interleaving and rotating the sets relative to each other.

For example, if the sets are $\{0,1,2,3\}$ and $\{4,5,6,7\}$, we could interleave them as $(4,0,5,1,6,2,7,3)$ and then rotate that to $(7,0,4,1,5,2,6,3)$ and so on. If the tuples were considered cyclical, than $n/2$ rotations (of step size 4) would suffice. For linear tuples, I could not find a better solution than doing $n/2-1$ rotations. In total $n-2$ tuples will be generated.

---

Implementing this recursively would be the most clean option, but since you explicitly asked for a function which takes a list and transforms it, I wrote a demo in Python of how the algorithm could look like. Notice that (implemented like this) it only works for $n=2^k$; but all $n$ should be doable with some minor modifications to the algorithm.

def rotate(L, groupsize):
    n = len(L)
    M = list(L)
    for k in range(n//groupsize//2):
        for i in range(groupsize):
            M[k*2*groupsize + 2*i] = L[k*2*groupsize + (2*i +2)%(2*groupsize)]
    return M

def combine(L, groupsize):
    n = len(L)
    M = n*[0]
    for k in range(n//groupsize//2):
        for i in range(groupsize):
            M[k*groupsize*2 + 2*i + 1] = L[i+k*groupsize*2]
            M[k*groupsize*2 + 2*i]   = L[i+k*groupsize*2+groupsize]
    return M

def generateTuples(n):
    L = list(range(n))
    yield L
    groupsize = 2
    while groupsize < n:
        L = combine(L, groupsize)
        yield L
        for _ in range(groupsize-1 if groupsize>2 else 0):
            L = rotate(L, groupsize)
            yield L
        groupsize *= 2