Есть ли алгоритм со сложностью O(n) для нахождения минимального количества перестановок элементов массива 1, чтобы массив 1 стал равен массиву 2?

Рейтинг: 3Ответов: 4Опубликовано: 24.08.2023

Есть 2 массива, элементы которых от 1 до n:

current_array = [1, 3, 5, 2, 4, 7, 6]
expected_array = [6, 2, 4, 1, 3, 5, 7]

Чтобы current_array стал равен expected_array за минимальное количество перестановок элементов current_array влево, нужно переставить 3 элемента:

current_array -> [4, 1, 3, 5, 2, 7, 6] -> [2, 4, 1, 3, 5, 7, 6] -> [6, 2, 4, 1, 3, 5, 7]

[6, 2, 4, 1, 3, 5, 7] == expected_array

Переставить - значит, подвинуть элемент t на p позиций влево, где p не больше, чем текущее количество элементов слева от t.

Чтобы найти минимальное количество перестановок, я написал такой код:

n = 7
current_array = [1, 3, 5, 2, 4, 7, 6]
expected_array = [6, 2, 4, 1, 3, 5, 7]
counter = 0

for i in range(n):
    if current_array[i] != expected_array[i]:
        current_array.remove(expected_array[i])
        current_array.insert(i, expected_array[i])
        counter += 1

print(counter)

Но его сложность O(n^2), что довольно медленно. Я думал использовать расстояние Левенштейна, но его сложность при равных массивах тоже будет равна O(n^2).

Есть ли алгоритм для этой задачи, сложность которого будет O(n)?

python массивы алгоритм сложность
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

Для решения этой задачи нужно определить порядок элементов в исходном массиве относительно целевого. Те элементы, которые расположены не по порядку, нуждаются в перемещении.

sa = [1, 3, 5, 2, 4, 7, 6]
ta = [6, 2, 4, 1, 3, 5, 7]

n = len(sa)
t = [0] * n
for i in range(n):
    t[ta[i] - 1] = i 
counter = 0
m = t[sa[0] - 1]
for i in range(1, n):
    a = t[sa[i] - 1]
    if a < m:
        counter += 1
    else:
        m = a

print(counter)

-->

3

Другие примеры:

Src [1, 3, 5, 2, 4, 7, 6]
Tgt [7, 6, 1, 3, 5, 2, 4]

2

Src [1, 2, 3, 4, 5]
Tgt [1, 2, 3, 4, 5]

0

Src [1, 2, 3, 4, 5]
Tgt [5, 4, 3, 2, 1]

4

Src [1, 2, 3, 4, 5]
Tgt [1, 2, 4, 3, 5]

1

Src [1, 2, 3, 4, 5]
Tgt [1, 5, 4, 3, 2]

3

Если элементам некоего множества можно поставить в соотвествие элементы множества соотвествующего количества последовательных натуральных чисел, то упорядочивание элементов такого множества осуществляется просто индексацией.

Этот код выводит промежуточный результат для демонстрации принципа решения:

n = len(sa)
t = [0] * n
tmp = [0] * n
for i in range(n):
    t[ta[i] - 1] = i 
for i in range(n):
    tmp[i] = t[sa[i] - 1] 
counter = 0
m = tmp[0]
for i in range(1, n):
    if tmp[i] < m:
        counter += 1
    else:
        m = tmp[i]

print('  Src', sa)
print('  Tgt', ta)
print('Order', tmp, '-->', counter)
▲ 2

Код:

def simplify(p, q):
    r = [None] * len(q)
    for i, j in enumerate(q, start=1):
        r[j - 1] = i
    return tuple(r[j - 1] for j in p)


def count(r):
    n = len(r)
    i = 0
    j = 1
    k = 0
    while j <= n:
        if r[i] < j:
            i += 1
        else:
            if r[i] > j:
                k += 1
            j += 1
    return k


print(count(simplify(
    tuple(map(int, input().split())),
    tuple(map(int, input().split()))
)))

Немного теории. Решение в вопросе верное. Можно показать, что если найдена оптимальная последовательность ходов, то её можно поменять на последовательность той же длины, которая ставит первый элемент на место, затем второй и т.д. Так что идея о "сборке" решения слева направо верная, хотя требуются усилия чтобы это доказать.

Практика. Упростим задачу - так переименуем числа в массивах, чтобы второй приобрёл вид 1 2 3 ... n. Например:

1 3 5 2 4 7 6    ->    4 5 6 2 3 7 1
6 2 4 1 3 5 7    ->    1 2 3 4 5 6 7

Ясно что исходная пара и новая пара решаются одним и тем же набором перемещений элементов - взаимное расположение элементов сохранилось.

Задача свелась к упорядочению массива слева направо и подсчёту числа шагов:

4 5 6 2 3 7 1
 /---------/    # единица на первое место
1 4 5 6 2 3 7
   /---/        # двойка на второе
1 2 4 5 6 3 7
     /---/      # тройка на третье
1 2 3 4 5 6 7

В коде в вопросе это делалось прямой модификацией первого массива. Можно обойтись без неё. Для этого один индекс заменим на пару: i и j.

оригинальное     решение без
решение          изменения
                 массива

i                i                 # i-тый элемент больше j (= 1)
4 5 6 2 3 7 1    4 5 6 2 3 7 1     # i не меняется
                 j = 1             # увеличиваем j

  i              i
1 4 5 6 2 3 7    4 5 6 2 3 7 1     # тоже самое для j = 2
                 j = 2

    i            i
1 2 4 5 6 3 7    4 5 6 2 3 7 1     # тоже самое для j = 3
                 j = 3

      i          i                 # i-тый элемент равен j (= 4)
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # перенос не нужен
                 j = 4             # двигаем и j и i

        i          i
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # снова равенство
                 j = 5

          i          i
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # опять
                 j = 6

            i          i           # i-тый элемент меньше j (= 7)
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # увеличиваем i чтобы пропустить
                 j = 7             # мусор

            i            i
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # снова пропускаем мусор
                 j = 7

            i              i       # i-тый элемент равен j (= 7)
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # перенос не нужен
                 j = 7             # двигаем и j и i

              i              i
1 2 3 4 5 6 7    4 5 6 2 3 7 1     # j вышел за пределы массива
                 j = 8             # завершаем цикл
▲ 2

А что если мы не будем передвигать массив, а сразу посчитаем для каждого элемента первого массива насколько далеко он находится от нужного положения, ведь если a стоит в первом массиве раньше чем во втором массиве, то передвинуть его можно только подставляя элементы перед ним.

▲ 0

Вариант без создания промежуточных списков со словарем и генератором. Не зависит от упорядоченности цифр от 1 до n.

def get_count(src: list[int], trg: list[int]) -> int:
    # Вариант генератора экономящий память за счет скорости
    # src_index_gen = (trg.index(src_item) for src_item in src)
    # Если размер памяти позволяет, то можно через словарь:
    trg_index = {n: i for i, n in enumerate(trg)}
    src_index_gen = (trg_index[src_item] for src_item in src)
    count: int = 0
    prev_item = next(src_index_gen)

    for next_item in src_index_gen:
        if prev_item > next_item:
            count += 1
        else:
            prev_item = next_item

    return count