5

В строке содержатся только буквы 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
2
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – Barmaley
    23 сен 2020 в 12:30
  • Для подобных задач лучше использовать сортировку подсчетом. За первый проход, используя букву как индекс в массиве счетчиков, вы узнаете, сколько раз встретилась данная буква. При втором проходе (уже по счетчикам!!!) вы выводите каждую букву нужное число раз.
    – avp
    23 сен 2020 в 22:30

2 ответа 2

2

Предлагаю следующий алгоритм нахождения минимального количества перестановок. Сложность 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
5
  • Если не ошибаюсь XZZYYYXXZYZZ должен выдавать 3, но первый вариант выдает 4. А YYZYZZXZXXYZZX, вроде как, должно быть 7, а получается 8.
    – braflovsky
    23 сен 2020 в 17:27
  • @braflovsky Да, есть проблема. Вместо того, чтобы сделать XYXYYYXZZZZZ -> XXXYYYYZZZZZ, программа делает XYXYYYXZZZZZ -> XXYYYYXZZZZZ -> XXXYYYYZZZZZ. Меняет Y с ближайшим X, а не с оптимальным.
    – MiniMax
    23 сен 2020 в 18:55
  • @braflovsky Сделал новую версию - идея такая же, как и в предыдущей, но исправлена проблема с неоптимальными перестановками.
    – MiniMax
    23 сен 2020 в 22:21
  • XZYXYXZXZXZYXZZYZZZY вроде как 6 должен выдавать, а выдает 7
    – braflovsky
    27 сен 2020 в 15:58
  • @braflovsky Проверил - если по шагам пройти алгоритм, видно, что всё-равно в некоторых местах переставляет неоптимально. В одном месте нужно было менять самый левый Z на X, тогда бы X прыгнул на своё место, а алгоритм поменял его на более поздний Z и X встал слишком далеко от общей последовательности X-ов, поэтому его пришлось переставлять дополнительно.
    – MiniMax
    27 сен 2020 в 17:49
1

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.