Алгоритм перестановки массива - PullRequest
Новая
       15

Алгоритм перестановки массива

0 голосов
/ 28 марта 2020

У нас есть целочисленный массив A[] размером N (1 ≤ N ≤ 10 ^ 4), который изначально является отсортированным массивом с записями 1...N. Для любой перестановки P размера N массив перетасовывается так, чтобы i -ая запись слева до шаффла находилась в Ai -ой позиции после шаффла. Вы будете повторять этот случайный порядок до тех пор, пока массив не будет снова отсортирован.

Например, для A[] = {1, 2, 3, 4}, если P = {1, 2, 3, 4}, для сортировки массива потребуется только один ход (записи переместятся в их исходные позиции). Если P = {4, 3, 1, 2}, то для повторной сортировки массива потребуется 4 шага: 

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]

Проблема состоит в том, чтобы найти сумму всех натуральных чисел J, для которых вы можете сгенерировать перестановку, которая требуется J перемещений для повторной сортировки массива.

Пример:

Для A[] = {1, 2, 3, 4} вы можете генерировать перестановки, которые требуют 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.

Некоторые наблюдения, которые я сделал, заключаются в том, что вы всегда можете сгенерировать перестановку, которая требует J ходов для (1 ≤ *). 1030 * <<code>N). Это потому, что в перестановке вы просто сдвинете на 1 все записи в диапазоне размеров J. Тем не менее, для перестановок, требующих J перемещений, где J ≥ N, вам потребуется другой алгоритм.

Решение методом грубой силы будет проверять каждую перестановку или N! перестановок, которые определенно не не подходит во время выполнения. Я ищу алгоритм с временем выполнения не более O (N ^ 2).

EDIT 1: всегда будет гарантирована перестановка, которая требует N ходов, так как вы можете создать перестановку, где каждая запись неуместна, а не просто поменялась местами с другой записью. Возникает вопрос, как найти перестановки, в которых J> N.

РЕДАКТИРОВАТЬ 2: @ljeabmreosn сделал замечание, что существует перестановка, которая принимает J шагов, если и только если существуют натуральные числа a_1 + ... + a_k = N и LCM(a_1, ..., a_k) = J. Таким образом, используя это наблюдение, проблема сводится к поиску всех разделов массива или разделов целого числа N. Тем не менее, это не будет квадратичный c алгоритм - как мне их эффективно найти?

1 Ответ

0 голосов
/ 30 марта 2020

Сумма различных порядков перестановок степени n.

https://oeis.org/A060179

Это число, которое вы ищете, с формулой и некоторым кленом code.

Как часто при попытке вычислить целочисленную последовательность, вычислите первые несколько значений (здесь 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
...