Равномерное распределение всех объектов в списке
У меня была эта проблема некоторое время, все еще пытаясь работать над решением.
Каков самый лучший метод для равномерного распределения объектов в списке с низким несоответствием?
Скажите, что у нас есть список или элементы в массиве:
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, но прямо сейчас все, о чем я забочусь, является методологией, как сделать это.
6 ответов
Просто небольшая идея: используйте отдельный список для каждого типа элементов. Затем, используя что-то вроде сортировки слиянием, вставьте по одному элементу из каждого списка в новый список, всегда в том же порядке. Пропускать пустые списки.
Это, конечно, не дает идеального решения, но его очень легко реализовать, и оно должно быть быстрым. Простое улучшение - отсортировать список по размеру, сначала наибольший. Это дает немного лучшие результаты, чем случайный порядок списков.
Обновление: , возможно, это могло бы улучшить ситуацию: получите размер самого большого списка при запуске алгоритма и назовите его LARGEST_SIZE - этот список получит свою очередь в каждом раунде. Теперь для всех остальных списков их следует использовать только в раундах start_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 раундов. Это действительно должно дать вам хороший интервал между элементами.
Это, конечно, хороший пример, для других чисел он становится немного уродливее. Для очень небольшого количества предметов это не даст вам идеальных результатов. Однако для большого количества предметов это должно работать неплохо.
Вы можете выполнить обратную кластеризацию K-средних , стремясь либо:
- максимизировать количество кластеров;
- определить близость элементов к аналогичным элементам, используя некую обратную функция, так что кластеры создаются из одинаковых элементов, которые находятся дальше друг от друга, а не близко друг к другу.
Я опубликую здесь решение, которое я использовал в нескольких случаях для этой проблемы в соревнованиях алгоритмов.
У вас будет максимальная куча пар (СЧЕТЧИК, ЦВЕТ), упорядоченных по СЧЕТЧИКУ, поэтому цвет с самым большим СЧЕТЧИКОМ будет наверху. Каждый раз у вас будет два случая: если значение вверху не равно последнему элементу в списке, вы удалите пару (COUNTERx, COLOURx) из кучи, добавьте COLOURx в конец списка, и добавьте пару ((COUNTERx) - 1, COLOURx) в кучу, если (COUNTERx) - 1! = 0. В другом случае возьмите вторую наибольшую пару COUNTER из кучи вместо первой и сделайте то же, что и для первой пары . Временная сложность равна o (S log N), где N - количество цветов, а S - размер списка.
Сортировка списка с использованием функции динамической оценки, которая для каждого элемента в списке возвращает расстояние от ближайшего элемента. с таким же значением.
Я думаю, что вам нужно будет оптимизировать для какой-то функции улучшения - скажем, рассчитать, насколько «лучше» будет вставить синий в определенное положение и сделать это для всех возможных позиций вставки, а затем вставить в любое место с максимальным значением этой функции «усиления» и продолжить.
Вы можете сгенерировать серию рациональных чисел, указывающих равные интервалы для каждого цвета. Затем отсортируйте все эти числа.
Пример:
- 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, чтобы удвоить счетчикB - установить
Rшаг для удвоения циклаRсчетчика -
- возьмите один из цветов с наименьшим счетчиком и поместите его в свой результат
- step, что счетчик с его шириной шага
- , пока все счетчики не станут> = 1
Поскольку вам нужно n шагов цикла, и каждый раз нужно найти минимум m чисел, это, кажется, выполняется на O (n · m) . Однако вы можете сохранить счетчики в минимальной куче, чтобы снова снизить ее до O (n · log m) .