Сколько нужно шагов, чтобы упорядочить буквы в строке O(nlogn)

Question

В строке содержатся только буквы X, Y или Z. Нужно упорядочить их по алфавиту в минимальное количество шагов. За один шаг можно менять местами две любые буквы. Например, упорядочить строку ZYXZYX оптимально за 3 шага: ZYXZYX -> XYXZYZ -> XXYZYZ -> XXYYZZ

ZZXXYY - за 4 шага, XXXX - соответственно за 0.

Как получить оптимальное количество шагов для сортировки через O(nlogn)?

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

def solve(s):
  n = len(s)
  newS = [*enumerate(s)] 
  sortedS = sorted(newS, key = lambda item:item[1])

  counter = 0
  vis = {v:False for v in range(n)} 
  print(newS)
  print(sortedS)

  for i in range(n):
    if vis[i] or sortedS[i][0] == i: 
      continue
    cycle_size = 0
    j = i 

    while not vis[j]: 
      vis[j] = True 
      j = sortedS[j][0] 
      cycle_size += 1
    
    if cycle_size > 0: 
      counter += (cycle_size - 1) 

  return counter

Answer 1

Предлагаю следующий алгоритм нахождения минимального количества перестановок. Сложность 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

Answer 2

В итоге решение получилось такое

def count(s):
    n = len(s)
    exist = list(s)
    target = sorted(exist)
    count = {"XY":0, "YX":0, "XZ":0, "ZX":0, "YZ":0, "ZY":0}
    left = n
    for i in range(n):
        if exist[i] == target[i]:
            left -= 1
            continue
        count[exist[i]+target[i]] += 1
    result = 0
    for each in [("XY","YX"),("XZ","ZX"),("YZ","ZY")]:
        swaps = min(count[each[0]],count[each[1]])
        result += swaps
        left -= swaps*2
    result += left//3*2
    return result

БЛОГ НА HUSL

Сколько нужно шагов, чтобы упорядочить буквы в строке O(nlogn)

Ответы (2 шт):