Разминка для ума

Первый список сортируем по возрастанию, пустые в конец. Из второго подбираем элементы (включая пустые ячейки) так, чтобы f была равна 0 для текущей пары. То есть, если во втором списке есть элемент, равный по значению, то его, иначе пустой (опять же, если есть). Потом приводим первый список к первоначальному виду, одновременно производя аналогичные перестановки и во втором. Таким образом получим неизмененный первый список и как-то хитро переставленный второй.

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

уменьшить сумму f(S1(i), S2(i)) i:=1..100 на наибольшее возможное значение.

уменьшить на наибольшее?

Привести к минимуму.

первое что пришло в голову:
1) отсортировать списки
2) тот, в котором меньше элементов разредить так, чтобы одинаковые элементы из двух списков имели один и тот же индекс.

ну или другими словами...:
удалить из более длинного списка все элементы имеющиеся в более коротком.

Если красивого решения не будет, попробуйте подойти как к оптимизационной задаче. Генетическим алгоритмом нагенерить цепочки перестановок.

1й цикл (минимизации по пустым): если обе ячейки пустые s1[i] == s2[i] == пустому - ищем j-й индекс, где обе ячейки s1[j] и s2[j] не пустые и не одинаковые, затем переставляем s1[i] и s1[j].
2й цикл (минимизация по одинаковым): для каждой ячейки i в s1 ищем соответствующий одинаковый элемент j в s2, если нашли такой и s1[j] - не пустой, то переставляем s1[i] и s1[j].

Также уже переставленные ячейки должны игнорироваться при поиске - нужно использовать битвектор для флага указывающего переставленные элементы. Очевидно, что любые другие перестановки не влияют на уменьшение итоговой суммы.
Сложность алгоритма - 2(N^2).

можно оптимизировать, если использовать хэш-таблицу для поиска.

удалять конечно же не обязательно, достаточно только найти нужные элементы и запомнить их индексы, тогда получится список пар (n, k), где n - индекс элемента в первом списке, а k - во втором. Ну и соответственно - необходимая перестановка.

пс пустой элемент - он ведь тоже имеет своё, некое абстрактное значение, потому сводится к равенству двух элементов опять же.

как ни странно основы теории групп - где про перестановки и их произведения.

по сути тебе нужно отдельно посчитать число пустых пар ( т.е когда в обоих списках пусто на данной позиции) число пар где одна из ячеек пустая и число равных элементов в 2ух списках ( кстати не сказано в одном списке могут быть повторяющиеся обьекты? - если да это несколько усложняет , далее будем считать , что в пределах списка объекты уникальны).

по результату если сума пустых пар и полупустых равно 100 - это конец, иначе

смотрим на пару равных . если они уже в одной отмечаем эту позицию как конечную. если нет то смотрим на их дополнения - если одно из дополнений пустое это откладываем на потом.

.....

короче при минимизации перестановок начни с разделения на пустые пары, полупустые , и пары содержащие в себе половинки из равных пар.

нужно для трьетих пар(2) подбирать пустую/полупустую которая после 2 перестановок образуют 3 конечные пары в худжем случае -

. в лучшем(дающем меньшее число необходимых перестановок) - возможны случае когда неподходящая пара образована из половинок имеющих себе равных-парных это приводит к удлинению цикла - цикл либо сам замыкается например случай 3 пар 1/2 2/3 3/1 либо по встречу на концах не парных элементов мы добавляя из резерва пустую пару получаем сырьё для n-перестановки дающей в итоге частичный ответ на этих парах .

так вся задача разбивается на циклы - если в какой то момент число пустых/полупустых пар закончилось - значит остальные концевые будут штрафные.