Есть ряд чисел от 1 до N. Каждое число может повторяться произвольное число раз. Необходимо преобразовать последовательность таким образом, чтобы одинаковые числа в ней располагались на одинаковом расстоянии друг от друга с минимальной погрешностью.
Пример:
Последовательность: 1 1 1 1 2 2 2 2 2 3 3 3 4
Результат: 2 1 3 2 1 3 2 1 3 2 1 4 2
Очевидно жадный алгоритм не подходит. Жадный с эвристиками, похоже, тоже не даст идеальных результатов.
Существуют ли какие-то уже разработанные подходы к реализации подобного рода "равномерных рассеиваний" ряда чисел?
UPD Расстояние между одинаковыми числами должно быть максимально возможным.
А чем не подходит обычная сортировка?:)
Не понял что Вы имеет в виду. Для простоты можно считать, что последовательность изначально остортирована. В задаче же требуется расставить числа по частоте их вхождений в исходную последовательность так, чтобы они по максимуму были равномерно распределены.
Видимо, перебор. Возможно, в него можно запихать какие-то отсечения, чтобы он работал немного быстрее факториала, но лучше ничего не могу придумать :\
Как минимум, это зависит от функционала качества;) Что-то мне подсказывает, что если взять как погрешность сумму модулей отклонений, ответ будет один, а если, скажем, корень из суммы квадратов отклонений — то совсем другой...
Подтерживаю, сортировка для данной задачи норм. Если там есть еще какие-то условия, которые делают невозможным это решение, то вы хотя бы написали о них.
Как уже правильно заметил DryukAlex, нужно знать критерий качества последовательности.
Да, и с какой целью Вы решаете эту задачу? Просто у меня валяются исходники моего тренажера для заучивания тестов, и я там реализовывал примерно то, про что Вы спрашиваете, получилась жуткая ботва с рандомом, тем не менее дававшая приемлемое (для моей задачи) распределение. Расскажу вкратце идею: я присваивал каждому элементу некий ключ примерно по такой формуле (возможно, формула на самом деле немного другая): (общее количество) / (количество элементов, равных данному) * (порядковый номер данного элемента среди ему равных) + (случайное число в некотором диапазоне), а затем сортировал элементы по этому ключу.
У меня были схожие мысли. В принципе, и реализация готова. Изначально же казалось, что должен быть какой-то готовый известный алгоритм на такую задачу для генерации идеально равномерного распределения, потому и спросил у сообщества.
Объясните же, наконец, что с Вашей точки зрения есть "идеально равномерное распределение"?! Я до сих пор ничего не понял, а ведь алгоритм для нужного Вам критерия, возможно, можно придумать.
Идеально — это как в примере. Когда между двумя одинаковыми цифрами всегда одно и то же количество других цифр.
А что делать в тех случаях, когда этого невозможно достичь? Простейший пример: 1 1 1 1 1 2 2 2.
1 2 1 2 1 2 1 1 Чем чаще встречается, тем критичнее чтобы числа не шли подряд.
Комментарий скрыт по желанию автора комментария
После комментария DryukAlex я дописал UPD к исходному посту.
Нашел в архивах вот такую задачу. Если интересно, то в ней ничего хорошего тогда не придумалось.
Похоже на мою, только мне сложнее — нужно еще и последовательность восстановить. В любом случае, спасибо. Поищу в интернете, может, кто-то её осилил.