Given $n$ and $k$, we want to find $k$ permutations that are most "scattered".
Background: I am trying to have multiple outputs using a greedy algorithm on a combinatorial optimization problem, which makes a decision for each node in a given order of the nodes. I want to have multiple trials that are as different as possible from each other. The nodes are assumed to be symmetric, and thus WLOG we can assume we always include $(1, 2, 3, \ldots, n)$.
Sorry for not having a rigorous definition. What I have in mind is when we have a circle, say, with radius $1$, then the most "scattered" three points can be $(\sin x, \cos x), (\sin (x + 2\pi/3), \cos (x + 2\pi/3)), (\sin (x + 4\pi/3), \cos (x + 4\pi/3))$, where $x$ can take any value due to the symmetry of a circle.
What can be an analogy in the space of all permutations?
Intuitively, for $k = 2$, we may have $(1, 2, 3, \ldots, n)$ and $(n, n-1, n-2, \ldots, 1)$.
I think we need to first decide which "distance" between permutations we want to use and then build up the corresponding metric space.
Any advice or comments would be highly appreciated.
Update: One of my friends mentioned a concept called "Latin Rectangle" (https://mathworld.wolfram.com/LatinRectangle.html). It seems useful to me. Would that be theoretically supported?