Algorithm for array permutation

Question

We have an integer array A[] of size N (1 ≤ N ≤ 10^4), which originally is a sorted array with entries 1...N. For any permutation P of size N, the array is shuffled so that i-th entry from the left before the shuffle is at the Ai-th position after the shuffle. You would keep repeating this shuffle until the array is sorted again.

For example, for A[] = {1, 2, 3, 4}, if P = {1, 2, 3, 4}, it would only take one move for the array to be sorted (the entries would move to their original positions). If P = {4, 3, 1, 2}, then it would take 4 moves for the array to be sorted again:

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]

The problem is to find the sum of all positive integers J for which you can generate a permutation that requires J moves to get the array sorted again.

Example:

For A[] = {1, 2, 3, 4}, you can generate permutations that require 1, 2, 3, and 4 steps:

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}

So you would output 1 + 2 + 3 + 4 = 10.

Some observations I have made is that you can always generate a permutation that requires J moves for (1 ≤ J < N). This is because in the permutation, you would simply shift by 1 all the entries in the range of size J. However, for permutations that requires J moves where J ≥ N, you would need another algorithm.

The brute-force solution would be checking every permutation, or N! permutations which definitely wouldn't fit in run time. I'm looking for an algorithm with run time at most O(N^2).

EDIT 1: A permutation that requires N moves will always be guaranteed as well, as you can create a permutation where every entry is misplaced, and not just swapped with another entry. The question becomes how to find permutations where J > N.

EDIT 2: @ljeabmreosn made the observation that there exists a permutation that takes J steps if and only if there are natural numbers a_1 + ... + a_k = N and LCM(a_1, ..., a_k) = J. So using that observation, the problem comes down to finding all partitions of the array, or partitions of the integer N. However, this won't be a quadratic algorithm - how can I find them efficiently?

Does this come from a certain programming competition? If so, it would be great to include a source. — ljeabmreosn
If I understand correctly, it looks like the goal is to compute the sum of the possible orders of an element in the Symmetric group of order N. — ljeabmreosn
It’s not the sum of all possible orders, but of all J where you can generate a permutation of length N that will need J shuffles to get the array sorted again. — user13133159
Yes, that is the definition of a permutation of order J. It's the minimum number of times with being composed with itself to return back to the original permutation. — ljeabmreosn
I don't think that algorithm will necessarily run in O(N^2), but it might help. Take a look at this: it might help with bounds. Note that there exists a permutation of order J if and only if there natural numbers a_1,...,a_k such that a_1 + ... + a_k = N and LCM(a_1,...,a_k) = J. Note that if a_1 + ... + a_k = N then a_1, ..., a_k is called a "partition of N". — ljeabmreosn

One Lyner One Lyner · Accepted Answer · 2020-03-30T13:19:51

Sum of distinct orders of degree-n permutations.

https://oeis.org/A060179

This is the number you are looking for, with a formula, and some maple code.

As often when trying to compute an integer sequence, compute the first few values (here 1, 1, 3, 6, 10, 21) and look for it in the great "On-line Encyclopedia of Integer Sequences".

Here is some python code inspired by it, I think it fits your complexity goals.

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]

on my machine:

>%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

1 Answers