Фон
Предположим, у меня есть две одинаковые партии из шариков. Каждый мрамор может быть одного из цветов c , где c≤n . Пусть n_i обозначает количество шариков цвета i в каждой партии.
Пусть - мультимножество представляющий один пакет. В частотном представлении , также может быть записана в виде .
Число различных перестановок задается мультиномиальная :
Вопрос
Существует ли эффективный алгоритм для генерации двух диффузных, ненормальных перестановок и из в случайном порядке? (Распределение должно быть равномерным.)
Перестановка является диффузным , если для каждого отдельного элемента из , экземпляры разнесены примерно равномерно в .
Например, предположим, что .
- не является диффузным
- является диффузным
Более строго:
- Если , существует только один экземпляр для «пробела» в , поэтому пусть .i P Δ ( i ) = 0
- В противном случае, пусть будет расстояние между экземпляра и экземпляра из в . Вычтите из него ожидаемое расстояние между экземплярами , определив следующее:
Если равномерно распределено в , то должно быть равно нулю или очень близко к нулю, если .j j + 1 i P i δ ( i , j ) = d ( i , j ) - n i P Δ ( i ) n i ∤ n
Теперь определим статистики , чтобы определить , сколько каждый равномерно разнесены в . Мы называем диффузным, если близко к нулю или примерно . (Можно выбрать пороговое значение специфичное для чтобы диффузным, если )i P P s ( P ) s ( P ) ≪ n 2 k ≪ 1 S P s ( P ) < k n 2
Это ограничение напоминает более строгую задачу планирования в реальном времени, называемую проблемой вращения, с мультимножеством (так что ) и плотностью . Цель состоит в том, чтобы запланировать циклическую бесконечную последовательность , чтобы любая подпоследовательность длины содержала, по меньшей мере, один экземпляр . Другими словами, выполнимое расписание требует все ; если плотно ( ), то и . Проблема с вертушкой, кажется, является NP-полной.a i = n / n i ρ = ∑ c i = 1 n i / n = 1 P a i i d ( i , j ) ≤ a i A ρ = 1 d ( i , j ) = a я s ( P ) = 0
Две перестановок и являются ненормальными , если представляет собой психоз из ; то есть для каждого индекса .Q
Например, предположим, что .
- и не являются ненормальными
- и являются ненормальными
Исследовательский анализ
Меня интересует семейство мультимножеств с и для . В частности, пусть .
Вероятность того, что два случайные перестановки и из являются ненормальными составляет около 3%.
Это можно рассчитать следующим образом, где - это й полином Лагерра: Смотрите здесь для объяснения.
Вероятность того, что случайная перестановка из является диффузной, составляет около 0,01%, устанавливая произвольный порог примерно на .
Ниже приведен график эмпирической вероятности 100 000 выборок где - случайная перестановка .
При средних размерах выборки .
Вероятность того, что две случайные перестановки действительны (как диффузная, так и ненормальная), составляет около .
Неэффективные алгоритмы
Обычный «быстрый» алгоритм для генерации случайного отклонения набора основан на отклонении:
сделать P ← случайная_перестановка ( D ) до is_derangement ( D , P ) возврат P
что занимает примерно итераций, поскольку существует примерно возможных неисправностей. Однако основанный на отбраковке рандомизированный алгоритм не был бы эффективен для этой задачи, так как он принимал бы порядок итераций.
В алгоритме, используемом Sage , случайное нарушение мультимножества «формируется путем случайного выбора элемента из списка всех возможных нарушений». Тем не менее, это тоже неэффективно, поскольку существует допустимых перестановок для перечисления, и, кроме того, для этого в любом случае потребуется алгоритм, просто выполняющий это.
Дальнейшие вопросы
В чем сложность этой проблемы? Может ли оно быть сведено к какой-либо знакомой парадигме, такой как сетевой поток, раскраска графа или линейное программирование?
Ответы:
Один из подходов: вы можете свести это к следующей проблеме: учитывая булеву формулу , выберите равномерно случайное назначение из всех удовлетворяющих назначений . Эта проблема NP-сложна, но существуют стандартные алгоритмы для генерации который приблизительно равномерно распределен, заимствуя методы из алгоритмов #SAT. Например, одна из техник состоит в том, чтобы выбрать хэш-функцию , диапазон которой имеет тщательно выбранный размер (примерно такой же, как число удовлетворяющих присваиваний ), случайным образом выбрать случайным образом значение из диапазонаφ(x) x φ(x) x h φ y h , а затем используйте SAT-решатель, чтобы найти удовлетворительное назначение для формулы . Чтобы сделать его эффективным, вы можете выбрать как разреженную линейную карту.φ(x)∧(h(x)=y) h
Это может быть отстрел блохи из пушки, но если у вас нет других подходов, которые кажутся работоспособными, вы можете попробовать это.
источник
некоторое расширенное обсуждение / анализ этой проблемы началось в чате cs с дополнительным фоном, который выявил некоторую субъективность в сложных требованиях проблемы, но не обнаружил никаких прямых ошибок или упущений.1
Вот некоторый протестированный / проанализированный код, который по сравнению с другим решением, основанным на SAT, является относительно «быстрым и грязным», но его было нетривиально / сложно отладить. он слабо концептуально основан на локальной псевдослучайной / жадной схеме оптимизации, чем-то похожей, например, на 2-OPT для TSP . Основная идея состоит в том, чтобы начать со случайного решения, которое соответствует некоторому ограничению, а затем возмущать его локально, чтобы искать улучшения, жадно искать улучшения и повторять их, и заканчивать, когда все локальные улучшения были исчерпаны. Критерии разработки заключались в том, что алгоритм должен быть максимально эффективным / избегать отклонений в максимально возможной степени.
есть некоторые исследования алгоритмов расстройства [4], например, используемые в SAGE [5], но они не ориентированы на мультимножества.
Простое возмущение - это только «перестановка» двух позиций в кортеже (ах). реализация в рубине. Ниже приведен обзор / примечания с ссылками на номера строк.
qb2.rb (gist-github)
подход здесь состоит в том, чтобы начать с двух ненормальных кортежей (# 106), а затем локально / жадно улучшить дисперсию (# 107), объединенную в концепции под названием
derangesperse
(# 97), сохраняя неисправность. обратите внимание, что обмен двух одинаковых позиций в паре кортежей сохраняет помехи и может улучшить дисперсию, и это (часть) дисперсного метода / стратегии.derange
подпрограмма работает слева направо на массиве (мультимножество) и свопы с элементами позже в массиве , где своп не с тем же элементом (# 10). Алгоритм завершается успешно, если без дальнейших перестановок в последней позиции два кортежа по-прежнему неисправны (# 16).Есть 3 различных подхода к сумасшедшим начальным кортежам. 2-й кортеж
p2
всегда тасуется. можно начать с кортежа 1 (p1
), упорядоченного поa.
«наивысшим степеням 1-го порядка» (# 128),b.
тасованному порядку (# 127)c.
и «наименьшим степеням 1-го порядка» («наивысшие степени последнего порядка») (# 126)процедура дисперсии
disperse
более сложна, но концептуально не так сложна. снова он использует свопы. вместо того, чтобы пытаться оптимизировать дисперсию в целом по всем элементам, он просто пытается итеративно смягчить текущий наихудший случай. Идея состоит в том, чтобы найти 1- й наименее рассредоточенный элемент слева направо. возмущение состоит в том, чтобы поменять местами левый или правый элементы (x, y
индексы) наименее рассредоточенной пары с другими элементами, но никогда между парой (что всегда уменьшит дисперсию), а также пропустить попытку замены с теми же элементами (select
в # 71) ,m
индекс средней точки пары (# 65).однако дисперсия измеряется / оптимизируется по обоим кортежам в паре (# 40) с использованием дисперсии «наименьший / левый» в каждой паре (# 25, # 44).
алгоритм пытается поменять местами самые дальние элементы 1- го (
sort_by / reverse
# 71).Существуют две разные стратегии
true, false
для решения, следует ли поменять местами левый или правый элемент наименьшей дисперсной пары (# 80), либо левый элемент для положения свопинга к левому / правому элементу с правой стороны, либо самый дальний левый или правый элемент в дисперсной паре от элемента подкачки.Алгоритм завершается (# 91), когда он больше не может улучшить дисперсию (либо смещает наихудшее место дисперсии вправо, либо увеличивает максимальную дисперсию по всей паре кортежей (# 85)).
статистика выводится для отклонений свыше
c
1000 отклонений по 3 подходам (# 116) иc
= 1000 переключений (# 97), рассматривая 2 дисперсных алгоритма для неисправной пары от отклонения (# 19, # 106). последний отслеживает общую среднюю дисперсию (после гарантированного расстройства). пример выполнения выглядит следующим образомэто показывает, что
a-true
алгоритм дает наилучшие результаты с ~ 92% неотрицания и средним наихудшим дисперсионным расстоянием ~ 2,6, и гарантированным минимумом 2 на 1000 испытаний, то есть по крайней мере 1 неравный промежуточный элемент между всеми парами одинаковых элементов. он нашел решения до 3 неравных промежуточных элементов.алгоритм отклонения - линейное предварительное отклонение по времени, а алгоритм дисперсии (работающий на нечувствительном входе), возможно, имеет значение ~ .O(nlogn)
1 проблема состоит в том, чтобы найти схемы пакетов викторины, которые удовлетворяют так называемому "фен шуй" [1] или "хорошему" случайному порядку, где "хороший" является несколько субъективным и еще не "официально" определенным количественно; автор проблемы проанализировал / свел ее к критериям отклонения / дисперсии, основанным на исследованиях сообщества викторин и «экспертов по фэн-шуй». [2] Есть разные идеи о «правилах фэн-шуй». Некоторое «опубликованное» исследование было сделано на алгоритмах, но оно появляется на ранних стадиях. [3]
[1] Пакет фэн-шуй / QBWiki
[2] Пакеты для викторины и фэн-шуй / Лифшиц
[3] Вопрос размещения , форум ресурсного центра HSQuizbowl
[4] Генерация случайных расстройств / Мартинес, Панхольцер, Продингер
[5] Алгоритм безумного ума (python) / McAndrew
источник