What kind of $x$ fits into $argsort(x)$=$ argsort(argsort(x))$

order-theorysorting

For a 1-d array, what kind of x gives you argsort(x) == argsort(argsort(x)) ? sorted array would be a trivial soliton. but you can have not sorted array like [1, 0, 2] or [1, 0, 2, 3]

argsort is function that returns the indices that would sort an array.

for example. given x=[1, 0, 10], argsort(x) would return [1, 0, 2] which represents the ordering of original array.

i'm really interested.

sorted_array = np.arange(10)

np.testing.assert_array_equal(np.argsort(sorted_array), 
                    np.argsort(np.argsort(sorted_array)))

# or
semi_sorted = [1, 0, 2]
np.testing.assert_array_equal(np.argsort(semi_sorted), 
                 np.argsort(np.argsort(semi_sorted)))

# or 

semi_sorted = [1, 0, 2, 3]

np.testing.assert_array_equal(np.argsort(semi_sorted),
               np.argsort(np.argsort(semi_sorted)))

what type of arrays fits in the criteria?

Best Answer

If I understand your $\operatorname{argsort}$ correctly, then $\operatorname{argsort}(x)$ takes as input a finite sequence of distinct numbers -- that is a map from $\{0,1,2,\ldots,n-1\}$ to distrinct numbers -- and produces a permutation $\sigma$ such that $x\circ\sigma$ is an increasing sequence.

Therefore, the fixed points of $\operatorname{argsort}$ are the permutations $\sigma$ where $\sigma\circ\sigma$ is an increasing sequence. But $\sigma\circ\sigma$ is always a permutation, and the only permutation that is increasing is the identity, so the fixed points are the $\sigma$ with $\sigma\circ\sigma=\rm Id$, or in other words permutations of order $1$ or $2$. That is exactly the permutations that are products of disjoint transpositions.

This is relevant because your equation $\operatorname{argsort}(x) = \operatorname{argsort}(\operatorname{argsort}(x))$ calls for $\operatorname{argsort}(x)$ to be a fixed point of $\operatorname{argsort}$.

Thus, the solutions to your equation are exactly the ones that you can make by:

  • Start with an increasing sequence.
  • Select zero or more non-overlapping pairs of elements in the sequence (not necessarily neighbors), and swap each pair.
Related Question