Равномерное распределение всех элементов в списке

Question

У меня была эта проблема некоторое время, я все еще пытался найти решение.

Каков наилучший из возможных способов равномерного распределения элементов в списке с низким расхождением?

Скажем, у нас есть список или элементы в массиве:

Red, Red, Red, Red, Red, Blue, Blue, Blue, Green, Green, Green, Yellow

Таким образом, в идеале вывод должен выглядеть примерно так:

Red, Blue, Red, Green, Red, Yellow, Blue, Red, Green, Red, Blue, Green.

Где каждый экземпляр находится "как можно дальше" от другого экземпляра самого себя ...

Когда я впервые попытался попробоватьЧтобы решить эту проблему, я должен признать, что я был наивен, поэтому я просто использовал некоторую форму случайного числа, чтобы перемешать список, но это приводит к скоплению экземпляров.

Предложение было начато с элемента с самой высокой частотой, поэтому красный будет помещен в позицию n * 12/5 для n от 0 до 4 включительно.

Затем поместите следующий наиболее повторяющийсяэлемент (синий) в положениях n * 12/3 + 1 для n от 0 до 2 включительно.Если что-то там уже размещено, просто поместите это в следующее пустое место.и т. д. и т. д. Однако, если записать это на бумаге, это не работает при всех обстоятельствах,

Скажем, список только

Red, Red, Red, Red, Red, Blue

Это не удастся.Там, где любой вариант имеет три смежных цвета одного цвета

Red, Red, Blue, Red, Red, Red
Red, Red, Red, Blue, Red, Red

Поэтому, пожалуйста, любые идеи или реализации, как это сделать, были бы замечательными.

Если это имеет значение, я работаю над целью-c, но сейчас все, что меня волнует, - это методология, как это сделать.

Answer 1

Просто быстрая идея: используйте отдельный список для каждого типа элемента. Затем, используя что-то вроде сортировки слиянием, вставьте один элемент из каждого списка в новый список, всегда в том же порядке. Пропустить пустые списки.

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

Обновление: возможно, это могло бы сделать его лучше: получите размер самого большого списка в начале алгоритма и назовите его LARGEST_SIZE - этот получит свой ход в каждом раунде. Теперь для всех остальных списков они должны использоваться только в starting_size_of_the_list/LARGEST_SIZE раундах. Я надеюсь, вы понимаете, о чем я. Таким образом, вы сможете равномерно распределить все элементы. Но, тем не менее, он все еще не совершенен!

ОК, поэтому я постараюсь быть более конкретным. Допустим, у вас есть 4 списка размеров: 30 15 6 3

Для первого списка вы будете использовать его каждый раунд 30/30, то есть 1, то есть каждый 1 раунд. Это значит каждый раз. Для второго списка вы будете использовать его 15/30, то есть 0,5, то есть каждые 2 раунда. третий список: 6/30 -> каждые 5 раундов. Последний список: 3/30 -> каждые 10 раундов. Это действительно должно дать вам хороший интервал предметов.

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

Answer 2

Вы можете сгенерировать серию рациональных чисел, указывающих четное расстояние для каждого цвета.Затем отсортируйте все эти числа.

Пример:

• 5 × B: числа равны (1/10 3/10 5/10 7/10 9/10)
• 3 × R: числа (1/6 3/6 5/6)
• отсортированы: ((1/10 "B") (1/6 "R") (3/10" B ") (5/10" B ") (3/6" R ") (7/10" B ") (5/6" R ") (9/10" B "))
• => BRBBRBRB

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

Обратите внимание, что отдельныйпоследовательности уже отсортированы, поэтому вы можете сортировать их путем слияния, что в данном случае составляет O (n · log m) ( n - сумма всех подсчетов, m количество цветов).Это может быть дополнительно оптимизировано путем ленивой генерации чисел.

Последний алгоритм не нуждается в явной сортировке:

• установите счетчик B в (/ (* 2 5)) => 1/10
• установите счетчик R на (/ (* 2 3)) => 1/6
• установите шаг B, чтобы удвоить Bcounter
• установите шаг R, чтобы удвоить R counter
• loop
  • выберите один из цветов с самым низким счетчиком и поместите его в свой результат
  • шаг этого счетчика по ширине шага
  • до тех пор, пока все счетчики не будут> = 1

Так как вам нужно n шаговцикла, и каждый раз, когда нужно найти минимум m чисел, это, кажется, работает на O (n · m) .Однако вы можете сохранить счетчики в минимальной куче, чтобы снова уменьшить их до O (n · log m) .

Answer 3

Я опубликую здесь решение, которое я использовал в нескольких случаях для этой задачи в конкурсах алгоритмов.

У вас будет максимальная куча пар (COUNTER, COLOR), упорядочить поСЧЕТЧИК, поэтому цвет с наибольшим счетчиком будет сверху.Каждый раз, когда у вас будет два случая: если значение в верхнем углу не равно последнему элементу в списке, вы удалите пару (COUNTERx, COLOURx) из кучи, добавьте COLOURx в конец списка,и добавьте пару ((COUNTERx) - 1, COLOURx) в кучу, если (COUNTERx) - 1! = 0. В другом случае возьмите вторую кучу пары COUNTER из кучи вместо первой и сделайте то же самое, что и для первой пары,Сложность по времени составляет o (S log N), где N - количество цветов, а S - размер списка.

Answer 4

Вы можете сделать обратную К-среднюю кластеризацию , стремясь либо:

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

Answer 5

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

Answer 6

Я думаю, вам нужно оптимизировать для какой-то функции улучшения - скажем, посчитать, насколько «лучше» будет вставить синий в определенной позиции и сделать это для всех возможных позиций вставки, а затем вставить в любое место с максимальным значением этой функции «усиления» и продолжайте.