Предлагаю следующий алгоритм нахождения минимального количества перестановок. Сложность O(n)
- выясняет необходимые перестановки за два прохода.
Объяснение
Понятно, что в итоговой строке все X
будут слева, а все Z
справа. Исходя из этого знания, при переборе строки можно все встречающиеся X
отправлять налево, а все Z
направо, Y
окажутся на своём месте автоматически. Можно сначала переместить все Z
, подсчитывая количество перестановок, потом перевернуть строку и используя ту же функцию, переместить все X
, не трогая отсортированную подстроку Z
, которая после переворачивания окажется в начале.
def number_of_permutations(string):
lst = list(string)
permutation_num = 0
def do_permutations(letter, left):
nonlocal permutation_num
right = len(lst) - 1
while left <= right:
cur_letter = lst[left]
if cur_letter == letter:
if cur_letter != lst[right]:
lst[left], lst[right] = lst[right], lst[left]
permutation_num += 1
right -= 1
else:
left += 1
return len(lst) - right
# Сначала ищём перестановки для буквы 'Z'
# Поиск начинаем с 0-го элемента, так как список ещё несортированный
new_start = do_permutations('Z', 0)
# Далее нужно найти перестановки буквы 'X'
# Переворачиваем список, чтобы не писать две практически одинаковые функции
# (в одном случае нужно искать от первого элемента к последнему,
# во втором от последнего к первому).
lst.reverse()
# И передаём перевёрнутый список в ту же самую функцию
# только поиск теперь начинается не с 0-го элемента, а с элемента,
# следующего за уже отсортированной подстрокой 'Z'.
do_permutations('X', new_start - 1)
# Переворачиваем список обратно
lst.reverse()
print(f"{string} -> {''.join(lst)}")
print(f"Количество перестановок: {permutation_num}")
print()
Тестирование
number_of_permutations("XYZXZY")
number_of_permutations("ZYZYXX")
number_of_permutations("ZXY")
number_of_permutations("ZXYZ")
number_of_permutations("XXXX")
number_of_permutations("ZZXXYY")
number_of_permutations("XZZYYYXXZYZZ")
number_of_permutations("YYZYZZXZXXYZZX")
Результат
XYZXZY -> XXYYZZ
Количество перестановок: 2
ZYZYXX -> XXYYZZ
Количество перестановок: 3
ZXY -> XYZ
Количество перестановок: 2
ZXYZ -> XYZZ
Количество перестановок: 2
XXXX -> XXXX
Количество перестановок: 0
ZZXXYY -> XXYYZZ
Количество перестановок: 4
XZZYYYXXZYZZ -> XXXYYYYZZZZZ
Количество перестановок: 3
YYZYZZXZXXYZZX -> XXXXYYYYZZZZZZ
Количество перестановок: 7