algorithm - 用于排序的重新洗牌次数

Question

我最近发现了一个有趣的问题，它看起来是这样的:

有一个沉闷的排序算法，它从数组中取第一个数，它找到一个比第一个元素低1的元素(或者当没有较低的元素时它取最高的元素一)，并把它放在前面。 将索引为 x(从 0 开始计数)的元素放在前面的成本等于它的索引。它会继续这个过程，直到数组被排序。 任务是统计排序所有n!从 1 到 n 的数字排列。答案可能很大，所以答案应该取模 m(n 和 m 在输入中给出)

示例:

Input (n,m): 3 40
Answer: 15

There are permutations of numbers from 1 to 3. The costs of sorting them are:
(1,2,3)->0
(1,3,2)->5
(2,1,3)->1
(2,3,1)->2
(3,1,2)->4
(3,2,1)->3
  sum = 15

我的程序生成了所有可能的数组并将它们一一排序。它的复杂度是 O(n!*n^2)，太高了。我被我所有的想法和这个蛮力解决方案困住了。

我还发现了一些有趣的事情:

1. 当我根据这些成本的数量对排序排列的成本进行分组时，我得到了一个奇怪的数字:n=7 https://cdn.discordapp.com/attachments/503942261051228160/905511062546292807/unknown.png(每行有 2 个数字 x * y，在它们之前有 y 个空格。x-排序成本，y-排序成本等于 y 的排列数 (1-n))。分数是所有行 x*y 的总和。如果需要，我可以为其他 n 提供这个数字。
2. 可能与斐波那契数有关，只是一种感觉。
3. 如您所见，图 1. 中有一段的所有 y 都相同。它从 x=n^2-4n+3 开始。

问题:如何更有效地解决这个问题？

Answer 1

排序算法有两个阶段:首先对排列进行排序进入身份的某种旋转，然后将其旋转到身份。我们分别计算这些阶段的成本。

第一阶段最多包含 n−2 步。在 n−1−j 移动之后，排列由 n−j 个值 x, x+1, x+2, … mod n 后跟一个剩余 j 值的排列，假设我们从一个随机排列，同样可能是在任何特定的顺序。我们必须移动 x−1 mod n 的预期距离是 ((n−j)+(n−1))/2。但是等一下，如果我们仍处于第一阶段，我们只会计算移动。因此，我们需要对排列已经是 a 的情况进行打折回转。有 n!/j!他们中的，他们最后都有 x−1，所以每个的折扣是 n−1。

第二阶段平均由 (n−1)/2 次移动组成到开头的排列，每个排列的成本为 n−1。平均费用总而言之!因此，排列是 (n−1)²/2。

我将在下面保留 Python 的模块化算法/强度约简作为练习。

from itertools import permutations
from math import factorial


# Returns the total cost of sorting all n-element permutations.
def fast_total_sort_cost(n):
    cost = 0
    for j in range(n - 1, 0, -1):
        cost += factorial(n) * ((n - j) + (n - 1)) // 2
        cost -= (factorial(n) // factorial(j)) * (n - 1)
    return cost + factorial(n) * (n - 1) ** 2 // 2


# Reference implementation and test.
def reference_total_sort_cost(n):
    return sum(sort_cost(perm) for perm in permutations(range(n)))


def sort_cost(perm):
    cost = 0
    perm = list(perm)
    while not is_sorted(perm):
        i = perm.index((perm[0] - 1) % len(perm))
        cost += i
        perm.insert(0, perm.pop(i))
    return cost


def is_sorted(perm):
    return all(perm[i - 1] <= perm[i] for i in range(1, len(perm)))


if __name__ == "__main__":
    for m in range(1, 9):
        print(fast_total_sort_cost(m), reference_total_sort_cost(m))