阵列排列算法-解网

问：

我们有一个大小为（1 ≤ ≤ 10^4）的整数数组，它最初是一个带有条目的排序数组。对于任何大小的排列，数组被洗牌，使得洗牌前左边的-th条目位于洗牌后的-th位置。您将不断重复此洗牌，直到数组再次排序。A[]NN1...NPNiAi

例如，对于，如果，只需移动一次即可对数组进行排序（条目将移动到其原始位置）。如果，则数组需要 4 次移动才能再次排序：A[] = {1, 2, 3, 4}P = {1, 2, 3, 4}P = {4, 3, 1, 2}

Move 0 | [1, 2, 3, 4]
Move 1 | [3, 4, 2, 1]
Move 2 | [2, 1, 4, 3]
Move 3 | [4, 3, 1, 2]
Move 4 | [1, 2, 3, 4]

问题在于找到所有正整数的总和，您可以为其生成一个排列，该排列需要移动才能再次对数组进行排序。JJ

例：

对于，您可以生成需要 1、2、3 和 4 个步骤的排列：A[] = {1, 2, 3, 4}

Requires 1 move: P = {1, 2, 3, 4}
Requires 2 moves: P = {1, 3, 2, 4}
Requires 3 moves: P = {1, 4, 2, 3}
Requires 4 moves: P = {4, 3, 1, 2}

因此，您将输出 1 + 2 + 3 + 4 = 10。

我所做的一些观察是，您总是可以生成需要移动的排列（1 ≤ < ）。这是因为在排列中，您只需将大小范围内的所有条目移动 1 即可。但是，对于需要移动到 ≥ 的排列，您将需要另一种算法。JJNJJJN

暴力解决方案是检查每个排列，或者绝对不适合运行时的排列。我正在寻找一种运行时间最多为 O（N^2）的算法。N!

编辑 1：需要移动的排列也将始终得到保证，因为您可以创建一个排列，其中每个条目都放错了位置，而不仅仅是与另一个条目交换。问题变成了如何找到排列，其中 > .NJN

编辑 2：@ljeabmreosn观察到存在一种排列，当且仅当存在自然数和时，该排列才会采取步骤。因此，使用该观察结果，问题归结为查找数组的所有分区或整数的分区。但是，这不是一个二次算法 - 我怎样才能有效地找到它们？Ja_1 + ... + a_k = NLCM(a_1, ..., a_k) = JN

数组算法优化语言无关的排列

我不认为该算法一定会运行，但它可能会有所帮助。看看这个：它可能有助于边界。请注意，当且仅当存在诸如和的自然数时，才存在顺序排列。请注意，如果 then 称为“分区”。O(N^2)Ja_1,...,a_ka_1 + ... + a_k = NLCM(a_1,...,a_k) = Ja_1 + ... + a_k = Na_1, ..., a_kN

答：

0赞 One Lyner 3/30/2020 #1

次 n 排列的不同阶数之和。

https://oeis.org/A060179

这是您要查找的数字，带有公式和一些枫木代码。

在尝试计算整数序列时，通常计算前几个值（此处为 1、1、3、6、10、21），并在伟大的“整数序列在线百科全书”中查找它。

这里有一些受它启发的 python 代码，我认为它符合你的复杂性目标。

def primes_upto(limit):
    is_prime = [False] * 2 + [True] * (limit - 1)
    for n in range(int(limit**0.5 + 1.5)):
        if is_prime[n]:
            for i in range(n*n, limit+1, n):
                is_prime[i] = False
    return [i for i, prime in enumerate(is_prime) if prime]

def sum_of_distinct_order_of_Sn(N):
    primes = primes_upto(N)
    res = [1]*(N+1)
    for p in primes:
        for n in range(N,p-1,-1):
            pj = p
            while pj <= n:
                res[n] += res[n-pj] * pj
                pj *= p
    return res[N]

在我的机器上：

>%time sum_of_distinct_order_of_Sn(10000)                                                                                                                                                           
CPU times: user 2.2 s, sys: 7.54 ms, total: 2.21 s
Wall time: 2.21 s
51341741532026057701809813988399192987996798390239678614311608467285998981748581403905219380703280665170264840434783302693471342230109536512960230

阵列排列算法

Algorithm for array permutation

评论

评论