Алгоритм сортировки для дорогостоящего обмена?

Question

Я столкнулся со следующей проблемой в разрабатываемом приложении:

Мне даны два списка:

list1 = {Z, K, A, B, A, C}

list2 = {A, A, B, C, K, Z}

list2 гарантированно будет отсортированной версией list1.

Моя цель - сортировать list1 только путем замены элементов в list1. Так, например, Я не могу перебрать list2 и просто назначить каждый элемент i в list1 каждому элементу j в list2.

Используя list2 в качестве ресурса, мне нужно отсортировать list1 в абсолютном минимальном количестве возможных перестановок .

Существует ли набор алгоритмов специально для этой цели? Я не слышал о такой вещи.

Answer 1

Я написал этот код в Java, чтобы сделать минимальные перестановки, Поскольку второй список гарантированно будет отсортирован, мы можем найти каждый элемент в нем и найти его индекс из первого списка, а затем выполнить обмен между текущим индексированным элементом и тем, который мы нашли.

Обновление : я изменил findLastElementIndex, так как он проверяет, будет ли замененный элемент в правильном индексе после замены на основе list2.

public class Testing {

    private static String[] unorderedList = {"Z", "C", "A", "B", "A", "K"};
    private static String[] orderedList = {"A", "A", "B", "C", "K", "Z"};
    private static int numberOfSwaps;

    public static void main(String[] args) {
        for (int i = 0; i < unorderedList.length; i++) {
            if (!unorderedList[i].equals(orderedList[i])) {
                int index = findElementToSwapIndex(i, orderedList[i]);
                swapElements(unorderedList, i, index);
            }
        }
        System.out.println(numberOfSwaps);
    }

    private static void swapElements(String[] list, int indexOfFirstElement, int IndexOfSecElement) {
        String temp = list[indexOfFirstElement];
        list[indexOfFirstElement] = list[IndexOfSecElement];
        list[IndexOfSecElement] = temp;
        numberOfSwaps++;
    }

    private static int findElementToSwapIndex(int currentIndexOfUnorderedList , String letter) {
        int lastElementToSwapIndex = 0;
        for (int i = 0; i < unorderedList.length; i++) {
            if (unorderedList[i].equals(letter)) {
                lastElementToSwapIndex = i;
            if(unorderedList[currentIndexOfUnorderedList].equals(orderedList[lastElementToSwapIndex])){// check if the swapped element will be in the right place in regard to list 2
                    return lastElementToSwapIndex;
                }
            }
        }
        return lastElementToSwapIndex;
    }
}

мин. Количество свопов для этого кода было таким же, как в https://stackoverflow.com/a/40507589/6726632

Надеюсь, это поможет вам.