Лексикографическая минимальная перестановка такая, что все смежные буквы различны

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

Итак, нам нужно выполнить алгоритм сортировки, который, например, сортирует "AAABBB" в ABABAB. Максимальный размер ввода - 10 ^ 6, и все это должно произойти менее 1 секунды. Если есть более одного ответа, первый в алфавитном порядке является правильным. Я начал тестировать различные алгоритмы, чтобы даже сортировать их без учета этого требования в алфавитном порядке, просто чтобы понять, как все сложилось.

Первая версия:

Сохраните коды ascii в массив Integer, где index - это код ascii, а значение - это количество, которое этот символ встречается в массиве char. Затем я выбрал 2 наивысших числа и начал рассылать их в новый массив символов после друг друга, пока какое-то число не было выше, и я поменялся на него. Он работал хорошо, но, конечно, порядок был неправильным.

Вторая версия:

Следуя той же идее, но перестала выбирать самое встречное число и просто выбрала индексы в том порядке, в котором они были в моем массиве. Хорошо работает, пока вход не будет похож на CBAYYY. Алгоритм сортирует его с ABCYYY вместо AYBYCY. Конечно, я мог бы попытаться найти некоторые свободные пятна для этих Y, но в этот момент он начинает занять слишком много времени.

Ответ 1

Интересная проблема с интересной настройкой. Да, это перестановка или перестановка, а не сортировка. Нет, цитируемый вопрос не является дубликатом.

Алгоритм.

Подсчитайте частоты символов.
Вывести чередующиеся символы из двух нижних в алфавитном порядке.
По мере исчерпания каждого из них перейдите к следующему.
В какой-то момент самая высокая частота char будет равна половине оставшихся символов. В этот момент переключитесь на вывод всего этого char, чередующегося поочередно с остальными символами в алфавитном порядке.

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

Обратите внимание, что существует один специальный случай, когда количество символов нечетно, а частота одного символа начинается с (половина плюс 1). В этом случае вам нужно начать с шага 4 в алгоритме, выведя все один символ, чередующийся с каждым из остальных по очереди.

Отметим также, что если один символ содержит более половины входных данных, то для этого частного случая не существует никакого решения. Эта ситуация может быть обнаружена заранее, проверяя частоты или во время выполнения, когда хвост состоит из всего одного символа. Обнаружение этого случая не было частью спецификации.

Поскольку никакой сортировки не требуется, сложность O (n). Каждый символ проверяется дважды: один раз, когда он подсчитывается, и один раз, когда он добавляется к выходу. Все остальное амортизируется.

Ответ 2

Вы начинаете с подсчета количества букв, которое у вас есть в вашем массиве:

Например, у вас есть 3 A, 2 B, 1 C, 4 Y, 1 Z.

1) Затем вы помещаете каждый раз нижний (это A), вы можете поставить.

поэтому вы начинаете с:

то вы не можете поставить A, чтобы вы положили B:

тогда:

ABABACYZ

Это работает, если у вас есть хотя бы 2 вида персонажей. Но здесь у вас будет еще 3 Y.

2) Чтобы поместить последние персонажи, вы просто переходите от первого Y и вставляете один на 2 в направлении начала. (Я не знаю, насколько это хороший способ сказать это на английском языке).

Итак, ABAYBYAYCYZ.

3) Затем вы берете subSequence между Y так YBYAYCY и сортируете букву между Y:

BAC = > ABC

И вы приходите

ABAYAYBYCYZ

который должен быть решением вашей проблемы.

Чтобы сделать все это, я думаю, что LinkedList - лучший способ

Я надеюсь, что это поможет:)

Ответ 3

Моя идея такова. При правильной реализации он может быть почти линейным.

Сначала установите функцию, чтобы проверить, возможно ли решение. Это должно быть очень быстро. Что-то вроде наиболее частого письмa > 1/2 всех букв и вставлять в cosideration, если оно может быть первым.

Затем, пока все еще остаются буквы, возьмите алфавитно первую букву, которая не совпадает с предыдущей, и делает возможным дальнейшее решение.

Ответ 4

Правильный алгоритм будет следующим:

Создайте гистограмму символов во входной строке.
Поместите CharacterOccurrences в PriorityQueue/TreeSet, где они упорядочены с наивысшим наименованием, наименьшим алфавитным порядком
Имейте вспомогательную переменную типа CharacterOccurrence
Петля, пока PQ не пуст
- Возьмите голову PQ и сохраните ее
- Добавление символа головы к выходу
- Если вспомогательная переменная установлена = > Повторно добавьте ее в PQ
- Храните сохраненную головку во вспомогательной переменной с 1 вхождением меньше, если вхождение не заканчивается 0 (затем отключает)
если размер вывода == размер ввода, это было возможно, и у вас есть свой ответ. Иначе это было невозможно.

Сложность - это O (N * log (N))

Ответ 5

Сделайте двунаправленную таблицу частот символов: character->count и count->character. Запишите a optional<Character>, в котором хранится последний символ (или ни один из них не существует). Сохраните общее количество символов.

Если (общее число символов-1) < 2 * (максимальное количество символов счетчика), используйте символ с наименьшим количеством символов счета. (иначе решения не было бы). Ошибка, если это последний вывод символа.

В противном случае используйте самый ранний алфавит, который не является последним символом.

Запишите последний выход символа, уменьшите как общее, так и использованное количество символов.

Петля, пока у нас все еще есть символы.

Ответ 6

В то время как этот вопрос не совсем повторяется, часть моего ответа дает алгоритм для перечисления все перестановки с как можно меньшим количеством смежных равных букв могут быть адаптированы для возврата только минимума, так как для доказательства оптимальности требуется, чтобы каждый рекурсивный вызов выводил по крайней мере одну перестановку. Степень изменений вне тестового кода заключается в том, чтобы попробовать ключи в отсортированном порядке и сломаться после обнаружения первого попадания. Время выполнения кода ниже является полиномиальным (O (n), если я беспокоился о лучших структурах данных), поскольку в отличие от его предка он не перечисляет все возможности.

Ответ david.pfx подсказывает логику: жадно берут наименьшее письмо, которое не устраняет все возможности, но, как он отмечает, детали тонкие.

from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange


def get_mode(count):
    return max(count.items(), key=itemgetter(1))[0]


def enum2(prefix, x, count, total, mode):
    prefix.append(x)
    count_x = count[x]
    if count_x == 1:
        del count[x]
    else:
        count[x] = count_x - 1
    yield from enum1(prefix, count, total - 1, mode)
    count[x] = count_x
    del prefix[-1]


def enum1(prefix, count, total, mode):
    if total == 0:
        yield tuple(prefix)
        return
    if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:
        yield from enum2(prefix, mode, count, total, mode)
    else:
        defect_okay = not prefix or count[prefix[-1]] * 2 > total
        mode = get_mode(count)
        for x in sorted(count.keys()):
            if defect_okay or [x] != prefix[-1:]:
                yield from enum2(prefix, x, count, total, mode)
                break


def enum(seq):
    count = Counter(seq)
    if count:
        yield from enum1([], count, sum(count.values()), get_mode(count))
    else:
        yield ()


def defects(lst):
    return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))


def test(lst):
    perms = set(permutations(lst))
    opt = min(map(defects, perms))
    slow = min(perm for perm in perms if defects(perm) == opt)
    fast = list(enum(lst))
    assert len(fast) == 1
    fast = min(fast)
    print(lst, fast, slow)
    assert slow == fast


for r in range(10000):
    test([randrange(3) for i in range(randrange(6))])