时间戳

首页 > 解决方案 > 使用排列对随机数组进行排序

python - 使用排列对随机数组进行排序

问题描述

我尝试通过将数组与自身置换来对数组进行排序（数组包含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]

因此，由于某种原因，使用未排序数组的第二个示例时的排列按预期返回排序数组，但无序数组的工作方式不同。

有谁知道为什么？或者，如果有一种更简单的方法可以使用排列或类似的方法进行排序，那就太好了。

标签： pythonsortingshuffle

解决方案

TL;博士

没有理由期望a = a[a]对数组进行排序。在大多数情况下，它不会。如果是巧合，可能会。

什么是操作c = b[a]？或应用排列

当您使用a通过改组获得的数组作为相同大小数组的range(n)掩码时，在数学意义上，您正在对 的元素应用排列。例如：bnb

a = [2,0,1]
b = np.array(['Alice','Bob','Charlie'])
print(b[a])
# ['Charlie' 'Alice' 'Bob']

在这个例子中，数组a表示排列(2 0 1)，它是一个长度为 3 的循环。由于循环的长度是 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']

请注意，我对bton 的元素使用了字符串，以避免将它们与索引混淆。当然，我可以使用以下数字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]，代表身份排列 id；因此，我们通过反复应用发现的排列a是b：

id ==一个^0

一个

一个^2

一个^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.

推荐阅读