CODEWITHSUNDEEP
numpysorting
yupbank
yupbank

Reputation: 265

what kind of x fits into argsort(x) == argsort(argsort(x))?

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]

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)))

# or

semi_sorted = [2, 1, 3, 4, 5]

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

what type of arrays fits in the criteria?

Upvotes: 1

Views: 213

Answers (1)

Paul Panzer
Paul Panzer

Reputation: 53079

To formalize @Alex Riley's intuition:

For any (zero based) permutation p we have argsort(p) = p^-1 because by definition of argsort p[argsort(p)] = [0,1,2,...] and [0,1,2,...] viewed as a permutation is the identity.

Now, no matter what x, argsort(x) is a permutation, so writing p for that we get p = p^-1 or, equivalently, p^2 = id.

What do permutations p that are self-inverse look like? If p is applied twice nothing changes, so if the first application of p moves x to y the second application of p must move y to x. As y may equal x p must therefore consist of flips of two elements and of elements that stay put. That is also sufficient.

We now know what argsort(x) looks like. What about x itself? Let us for simplicity assume x has only unique elements, otherwise the details of the sort algorithm used have to be considered. Let us write s for the sorted x. Then s = x[p]. Permuting both sides with p we get s[p] = x[p^2] = x. So x may be any sequence that is obtained from an ordered sequence by flipping the positions of some (possibly zero) nonoverlapping pairs.

Upvotes: 1

Related Questions