numpy - 什么样的 x 适合 argsort(x) == argsort(argsort(x))？

Question

对于一维数组，什么样的 x 给你argsort(x) == argsort(argsort(x))？排序后的数组将是一个微不足道的孤子。但你可以没有排序数组喜欢[1, 0, 2]或[1, 0, 2, 3]

我真的很感兴趣。

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

什么类型的数组符合标准？

标签： numpysorting

Answer 1

将@Alex Riley 的直觉形式化：

对于任何（基于零的）排列 p 我们有 argsort(p) = p^-1 因为根据 argsort p[argsort(p)] = [0,1,2,...] 和 [0,1,2 ,...] 被视为排列的是同一性。

现在，无论 x 是什么，argsort(x) 都是一个排列，所以写出 p 得到 p = p^-1 或者等价地 p^2 = id。

自逆的排列 p 是什么样的？如果 p 被应用两次，则没有任何变化，因此如果 p 的第一次应用将 x 移动到 y，则 p 的第二次应用必须将 y 移动到 x。由于 y 可能等于 xp 因此必须由两个元素的翻转和保持不变的元素组成。这也足够了。

我们现在知道 argsort(x) 长什么样了。x 本身呢？为简单起见，我们假设 x 只有唯一元素，否则必须考虑使用的排序算法的细节。让我们为排序后的 x 写 s。那么 s = x[p]。用 p 置换两边，我们得到 s[p] = x[p^2] = x。因此 x 可以是通过翻转一些（可能为零）非重叠对的位置从有序序列中获得的任何序列。