用于排序的重新洗牌次数

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)，太高了。我被我所有的想法和这个蛮力解决方案困住了。

还有一些有趣的发现：

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

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

Answer 1

从排序后的排列 123...n，您可以使用规则的反向构建树，并获得所有排列。看到这棵树 n=4.

现在，观察一下

if node==1234 then cost(node) = 0

if node!=1234 then cost(node) = blue_label(node) + cost(parent)

你需要的是制定反向规则来生成树。也许使用一些记忆技术来避免每次都重新计算成本。

Answer 2

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

第一阶段最多包含n−2步。在 n−1−j 移动之后，排列由 n−j 个值 x, x+1, x+2, … mod n 后跟 a 剩余 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.

我将 modular arithmetic/strength 减少 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))

用于排序的重新洗牌次数

Number of reshuffles used to sort

sorting

algorithm

sequence

factorial

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