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: