使用排列对随机数组进行排序
Sorting a random array using permutation
我试图通过排列数组本身来对数组进行排序
（该数组包含 0 到其 length-1 范围内的所有数字）
所以为了测试它我使用了 random.shuffle 但它有一些意想不到的结果
a = np.array(range(10))
random.shuffle(a)
a = a[a]
a = a[a]
print(a)
# not a sorted array
# [9 5 2 3 1 7 6 8 0 4]
a = np.array([2,1,4,7,6,5,0,3,8,9])
a = a[a]
a = a[a]
print(a)
# [0 1 2 3 4 5 6 7 8 9]
所以出于某种原因，使用未排序数组的第二个示例时的排列 returns 按预期排序的数组，但打乱的数组的工作方式不同。
有谁知道为什么？或者，如果有更简单的方法使用排列或类似的方法进行排序，那就太好了。
TL;DR
没有理由期望 a = a[a] 对数组进行排序。大多数情况下不会。万一巧合呢。
什么操作c = b[a]？或 应用排列
当您使用通过混洗 range(n) 获得的数组 a 作为相同大小 n 的数组 b 的掩码时，您正在应用 排列，在数学意义上，对b的元素。例如：
a = [2,0,1]
b = np.array(['Alice','Bob','Charlie'])
print(b[a])
# ['Charlie' 'Alice' 'Bob']
在这个例子中，数组a表示排列(2 0 1)，这是一个长度为3的循环。由于循环的长度是3，如果你应用它三次，你会在你开始的地方结束：
a = [2,0,1]
b = np.array(['Alice','Bob','Charlie'])
c = b
for i in range(3):
c = c[a]
print(c)
# ['Charlie' 'Alice' 'Bob']
# ['Bob' 'Charlie' 'Alice']
# ['Alice' 'Bob' 'Charlie']
请注意，我对 b 的元素使用了字符串，以避免将它们与索引混淆。当然，我可以使用 range(n):
中的数字
a = [2,0,1]
b = np.array([0,1,2])
c = b
for i in range(3):
c = c[a]
print(c)
# [2 0 1]
# [1 2 0]
# [0 1 2]
您可能会看到一个有趣但不足为奇的事实：第一行等于 a；换句话说，将 a 应用于 b 的第一个结果等于 a 本身。这是因为b被初始化为[0 1 2]，代表identity permutation id；因此，我们通过将 a 重复应用于 b 找到的排列是：
id == a^0
a
a^2
a^3 == id
我们总能回到起点吗？或 排列的秩
代数的一个众所周知的结果是，如果你一次又一次地应用相同的排列，你最终会得到恒等排列。在代数符号中：对于每个排列 a，存在一个整数 k 使得 a^k == id.
我们能猜出k的值吗？
k的最小值称为排列的秩。
如果a是一个循环，那么最小可能的k就是循环的长度。在我们前面的例子中，a 是一个长度为 3 的循环，因此在我们再次找到恒等排列之前需要三次应用 a。
长度为2的循环怎么样？长度为2的循环就是“交换两个元素”。例如，交换元素 0 和 1：
a = [1,0,2]
b = np.array([0,1,2])
c = b
for i in range(2):
c = c[a]
print(c)
# [1 0 2]
# [0 1 2]
我们交换 0 和 1，然后我们将它们交换回来。
两个不相交的循环怎么样？让我们在前三个元素上尝试一个长度为 3 的循环，同时交换最后两个元素：
a = [2,0,1,3,4,5,7,6]
b = np.array([0,1,2,3,4,5,6,7])
c = b
for i in range(6):
c = c[a]
print(c)
# [2 0 1 3 4 5 7 6]
# [1 2 0 3 4 5 6 7]
# [0 1 2 3 4 5 7 6]
# [2 0 1 3 4 5 6 7]
# [1 2 0 3 4 5 7 6]
# [0 1 2 3 4 5 6 7]
仔细查看中间结果可以看出，前三个元素有一个长度为 3 的周期，后两个元素有一个长度为 2 的周期。总周期是两个周期的最小公倍数，即6.
什么是一般的k？一个著名的代数定理指出：每个排列都可以写成作为不相交循环的产物。循环的秩是循环的长度。不相交循环乘积的秩是循环秩的最小公倍数。
你代码中的一个巧合：排序 [2,1,4,7,6,5,0,3,8,9]
让我们回到您的 python 代码。
a = np.array([2,1,4,7,6,5,0,3,8,9])
a = a[a]
a = a[a]
print(a)
# [0 1 2 3 4 5 6 7 8 9]
你应用了多少次排列 a？ 请注意，由于赋值 a =，数组 a 在第一次之间发生了变化第二行 a = a[a]。让我们通过为每个不同的值使用不同的变量名称来消除一些混淆。您的代码相当于：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a2 = a[a]
a4 = a2[a2]
print(a4)
或等价地：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = (a[a])[a[a]]
最后一行看起来有点复杂。然而，代数的一个很酷的结果是排列组合是关联。您已经知道加法和乘法是关联的：x+(y+z) == (x+y)+z 和 x(yz) == (xy) z。好吧，事实证明排列的组合也是结合的！使用 numpy 的掩码，这意味着：
a[b[c]] == (a[b])[c]
因此您的 python 代码等同于：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = ((a[a])[a])[a]
print(a4)
或者没有不需要的括号：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = a[a][a][a]
print(a4)
因为 a4 是恒等排列，这告诉我们 a 的秩被 4 除。因此 a 的秩是 1, 2或 4. 这告诉我们 a 可以写成交换和长度为 4 的循环的乘积。排名 1 的唯一排列是身份本身。秩为 2 的排列是不相交交换的产物，我们可以看到 a 不是这种情况。因此 a 的等级必须正好是 4.
你可以通过选择一个元素，并沿着它的轨道找到循环：那个元素依次转化成什么值？在这里我们看到：
- 0转化为2； 2转化为4； 4转化为6； 6转化为0;
- 1 个保持不变；
- 3变成7； 7 变成 3;
- 5未动； 8 和 9 未动。
结论： 你的 numpy 数组代表排列 (0 -> 2 -> 4 -> 6 -> 0)(3 <-> 7) ，其秩为4和2的最小公倍数，lcm(4,2) == 4.
花了一些时间，但我想出了一个办法。
numpy 没有这个功能，但 panda 有。
通过使用 df.reindex 我可以通过索引对数据框进行排序
import pandas as pd
import numpy as np
train_df = pd.DataFrame(range(10))
train_df = train_df.reindex(np.random.permutation(train_df.index))
print(train_df) # random dataframe contaning all values up to 9
train_df = train_df.reindex(range(10))
print(train_df) # sort data frame
我试图通过排列数组本身来对数组进行排序
（该数组包含 0 到其 length-1 范围内的所有数字）
所以为了测试它我使用了 random.shuffle 但它有一些意想不到的结果
a = np.array(range(10))
random.shuffle(a)
a = a[a]
a = a[a]
print(a)
# not a sorted array
# [9 5 2 3 1 7 6 8 0 4]
a = np.array([2,1,4,7,6,5,0,3,8,9])
a = a[a]
a = a[a]
print(a)
# [0 1 2 3 4 5 6 7 8 9]
所以出于某种原因，使用未排序数组的第二个示例时的排列 returns 按预期排序的数组，但打乱的数组的工作方式不同。
有谁知道为什么？或者，如果有更简单的方法使用排列或类似的方法进行排序，那就太好了。
TL;DR
没有理由期望 a = a[a] 对数组进行排序。大多数情况下不会。万一巧合呢。
什么操作c = b[a]？或 应用排列
当您使用通过混洗 range(n) 获得的数组 a 作为相同大小 n 的数组 b 的掩码时，您正在应用 排列，在数学意义上，对b的元素。例如：
a = [2,0,1]
b = np.array(['Alice','Bob','Charlie'])
print(b[a])
# ['Charlie' 'Alice' 'Bob']
在这个例子中，数组a表示排列(2 0 1)，这是一个长度为3的循环。由于循环的长度是3，如果你应用它三次，你会在你开始的地方结束：
a = [2,0,1]
b = np.array(['Alice','Bob','Charlie'])
c = b
for i in range(3):
c = c[a]
print(c)
# ['Charlie' 'Alice' 'Bob']
# ['Bob' 'Charlie' 'Alice']
# ['Alice' 'Bob' 'Charlie']
请注意，我对 b 的元素使用了字符串，以避免将它们与索引混淆。当然，我可以使用 range(n):
a = [2,0,1]
b = np.array([0,1,2])
c = b
for i in range(3):
c = c[a]
print(c)
# [2 0 1]
# [1 2 0]
# [0 1 2]
您可能会看到一个有趣但不足为奇的事实：第一行等于 a；换句话说，将 a 应用于 b 的第一个结果等于 a 本身。这是因为b被初始化为[0 1 2]，代表identity permutation id；因此，我们通过将 a 重复应用于 b 找到的排列是：
id == a^0
a
a^2
a^3 == id
我们总能回到起点吗？或 排列的秩
代数的一个众所周知的结果是，如果你一次又一次地应用相同的排列，你最终会得到恒等排列。在代数符号中：对于每个排列 a，存在一个整数 k 使得 a^k == id.
我们能猜出k的值吗？
k的最小值称为排列的秩。
如果a是一个循环，那么最小可能的k就是循环的长度。在我们前面的例子中，a 是一个长度为 3 的循环，因此在我们再次找到恒等排列之前需要三次应用 a。
长度为2的循环怎么样？长度为2的循环就是“交换两个元素”。例如，交换元素 0 和 1：
a = [1,0,2]
b = np.array([0,1,2])
c = b
for i in range(2):
c = c[a]
print(c)
# [1 0 2]
# [0 1 2]
我们交换 0 和 1，然后我们将它们交换回来。
两个不相交的循环怎么样？让我们在前三个元素上尝试一个长度为 3 的循环，同时交换最后两个元素：
a = [2,0,1,3,4,5,7,6]
b = np.array([0,1,2,3,4,5,6,7])
c = b
for i in range(6):
c = c[a]
print(c)
# [2 0 1 3 4 5 7 6]
# [1 2 0 3 4 5 6 7]
# [0 1 2 3 4 5 7 6]
# [2 0 1 3 4 5 6 7]
# [1 2 0 3 4 5 7 6]
# [0 1 2 3 4 5 6 7]
仔细查看中间结果可以看出，前三个元素有一个长度为 3 的周期，后两个元素有一个长度为 2 的周期。总周期是两个周期的最小公倍数，即6.
什么是一般的k？一个著名的代数定理指出：每个排列都可以写成作为不相交循环的产物。循环的秩是循环的长度。不相交循环乘积的秩是循环秩的最小公倍数。
你代码中的一个巧合：排序 [2,1,4,7,6,5,0,3,8,9]
让我们回到您的 python 代码。
a = np.array([2,1,4,7,6,5,0,3,8,9])
a = a[a]
a = a[a]
print(a)
# [0 1 2 3 4 5 6 7 8 9]
你应用了多少次排列 a？ 请注意，由于赋值 a =，数组 a 在第一次之间发生了变化第二行 a = a[a]。让我们通过为每个不同的值使用不同的变量名称来消除一些混淆。您的代码相当于：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a2 = a[a]
a4 = a2[a2]
print(a4)
或等价地：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = (a[a])[a[a]]
最后一行看起来有点复杂。然而，代数的一个很酷的结果是排列组合是关联。您已经知道加法和乘法是关联的：x+(y+z) == (x+y)+z 和 x(yz) == (xy) z。好吧，事实证明排列的组合也是结合的！使用 numpy 的掩码，这意味着：
a[b[c]] == (a[b])[c]
因此您的 python 代码等同于：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = ((a[a])[a])[a]
print(a4)
或者没有不需要的括号：
a = np.array([2,1,4,7,6,5,0,3,8,9])
a4 = a[a][a][a]
print(a4)
因为 a4 是恒等排列，这告诉我们 a 的秩被 4 除。因此 a 的秩是 1, 2或 4. 这告诉我们 a 可以写成交换和长度为 4 的循环的乘积。排名 1 的唯一排列是身份本身。秩为 2 的排列是不相交交换的产物，我们可以看到 a 不是这种情况。因此 a 的等级必须正好是 4.
你可以通过选择一个元素，并沿着它的轨道找到循环：那个元素依次转化成什么值？在这里我们看到：
- 0转化为2； 2转化为4； 4转化为6； 6转化为0;
- 1 个保持不变；
- 3变成7； 7 变成 3;
- 5未动； 8 和 9 未动。
结论： 你的 numpy 数组代表排列 (0 -> 2 -> 4 -> 6 -> 0)(3 <-> 7) ，其秩为4和2的最小公倍数，lcm(4,2) == 4.
花了一些时间，但我想出了一个办法。 numpy 没有这个功能，但 panda 有。 通过使用 df.reindex 我可以通过索引对数据框进行排序
import pandas as pd
import numpy as np
train_df = pd.DataFrame(range(10))
train_df = train_df.reindex(np.random.permutation(train_df.index))
print(train_df) # random dataframe contaning all values up to 9
train_df = train_df.reindex(range(10))
print(train_df) # sort data frame