Эффективный алгоритм для генерации двух диффузных, ненормальных перестановок мультимножества в случайном порядке

13

Фон

Предположим, у меня есть две одинаковые партии из шариков. Каждый мрамор может быть одного из цветов c , где c≤n . Пусть n_i обозначает количество шариков цвета i в каждой партии.nccnnii

Пусть S - мультимножество {1,,1n1,2,,2n2,,1c,,cnc} представляющий один пакет. В частотном представлении , S также может быть записана в виде (1n12n2cnc) .

Число различных перестановок S задается мультиномиальная :

|SS|=(nn1,n2,,nc)=n!n1!n2!nc!=n!i=1c1ni!.

Вопрос

Существует ли эффективный алгоритм для генерации двух диффузных, ненормальных перестановок P и Q из S в случайном порядке? (Распределение должно быть равномерным.)

  • Перестановка P является диффузным , если для каждого отдельного элемента i из P , экземпляры i разнесены примерно равномерно в P .

    Например, предположим, что S=(1424)={1,1,1,1,2,2,2,2} .

    • {1,1,1,2,2,2,2,1} не является диффузным
    • {1,2,1,2,1,2,1,2} является диффузным

    Более строго:

    • Если , существует только один экземпляр для «пробела» в , поэтому пусть .i P Δ ( i ) = 0ni=1iPΔ(i)=0
    • В противном случае, пусть будет расстояние между экземпляра  и экземпляра  из в . Вычтите из него ожидаемое расстояние между экземплярами , определив следующее: Если равномерно распределено в , то должно быть равно нулю или очень близко к нулю, если .j j + 1 i P i δ ( i , j ) = d ( i , j ) - nd(i,j)jj+1iPi i P Δ ( i ) n in
      δ(i,j)=d(i,j)nniΔ(i)=j=1ni1δ(i,j)2
      iPΔ(i)nin

    Теперь определим статистики , чтобы определить , сколько каждый равномерно разнесены в . Мы называем диффузным, если близко к нулю или примерно . (Можно выбрать пороговое значение специфичное для чтобы диффузным, если )i P P s ( P ) s ( P ) n 2 k 1 S P s ( P ) < k n 2s(P)=i=1cΔ(i)iPPs(P)s(P)n2k1SPs(P)<kn2

    Это ограничение напоминает более строгую задачу планирования в реальном времени, называемую проблемой вращения, с мультимножеством (так что ) и плотностью . Цель состоит в том, чтобы запланировать циклическую бесконечную последовательность , чтобы любая подпоследовательность длины содержала, по меньшей мере, один экземпляр . Другими словами, выполнимое расписание требует все ; если плотно ( ), то и . Проблема с вертушкой, кажется, является 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 ) = 0A=n/Sai=n/niρ=i=1cni/n=1Paiid(i,j)aiAρ=1d(i,j)=ais(P)=0

  • Две перестановок и являются ненормальными , если представляет собой психоз из ; то есть для каждого индекса .QPQPQPiQii[n]

    Например, предположим, что .S=(1222)={1,1,2,2}

    • {1,2,1,2} и не являются ненормальными{1,1,2,2}
    • {1,2,1,2} и являются ненормальными{2,1,2,1}

Исследовательский анализ

Меня интересует семейство мультимножеств с и для . В частности, пусть .n=20ni=4i4D=(1424344352617181)

  • Вероятность того, что два случайные перестановки и из являются ненормальными составляет около 3%.PQD

    Это можно рассчитать следующим образом, где - это й полином Лагерра: Смотрите здесь для объяснения.Lkk

    |DD|=0dteti=1cLni(t)=0dtet(L4(t))3(L3(t))(L2(t))(L1(t))3=4.5×1011|SD|=n!i=1c1ni!=20!(4!)3(3!)(2!)(1!)3=1.5×1013p=|DD|/|SD|0.03
  • Вероятность того, что случайная перестановка из является диффузной, составляет около 0,01%, устанавливая произвольный порог примерно на .PDs(P)<25

    Ниже приведен график эмпирической вероятности 100 000 выборок где - случайная перестановка .s(P)PD

    При средних размерах выборки .s(P)Gamma(α8,β18)

    Ps(P)cdf(s(P)){1,8,2,3,4,1,5,2,3,6,1,4,2,3,7,1,5,2,4,3}1191<105{8,2,3,4,1,6,5,2,3,4,1,7,1,2,3,5,4,1,2,3}140916<104{3,6,5,1,3,4,2,1,2,7,8,5,2,4,1,3,3,2,1,4}650972<10.05{3,1,3,4,8,2,2,1,1,5,3,3,2,6,4,4,2,1,7,5}12239136<10.45{4,1,1,4,5,5,1,3,3,7,1,2,2,4,3,3,8,2,2,6}16979189<10.80

Вероятность того, что две случайные перестановки действительны (как диффузная, так и ненормальная), составляет около .v(0.03)(0.0001)21010

Неэффективные алгоритмы

Обычный «быстрый» алгоритм для генерации случайного отклонения набора основан на отклонении:

сделать
     P ← случайная_перестановка ( D )
до is_derangement ( D , P )
возврат P

что занимает примерно итераций, поскольку существует примерно возможных неисправностей. Однако основанный на отбраковке рандомизированный алгоритм не был бы эффективен для этой задачи, так как он принимал бы порядок итераций.en!/e1/v1010

В алгоритме, используемом Sage , случайное нарушение мультимножества «формируется путем случайного выбора элемента из списка всех возможных нарушений». Тем не менее, это тоже неэффективно, поскольку существует допустимых перестановок для перечисления, и, кроме того, для этого в любом случае потребуется алгоритм, просто выполняющий это.v|SD|21016

Дальнейшие вопросы

В чем сложность этой проблемы? Может ли оно быть сведено к какой-либо знакомой парадигме, такой как сетевой поток, раскраска графа или линейное программирование?

hftf
источник
Что касается вашего определения «с интервалом», разве вы не хотите, чтобы для с как страж? То есть, один элемент должен быть посередине, два должны разделить перестановку на трети и так далее. d(i,j)n/(ni+1)0ijn+1P0=Pn+1=i
Рафаэль
Что произойдет, если для зла (маленький, но достаточно большой); у нас вообще есть диффузные перестановки? Мы, конечно, не можем найти двух ненормальных! Кажется, что ни один элемент не может встречаться более раз. S={1nk,2k}kn/2
Рафаэль
1
Каково соотношение всех пар ненормальных перестановок среди всех пар диффузных перестановок? Точно так же, из всех пар ненормальных перестановок, сколько состоит из двух диффузных? (Если какое-либо соотношение «высокое», мы можем сосредоточить свои усилия на одной половине процесса, оставив другую на отклонении.)
Рафаэль
1
@Raphael (# 3а) Из 1 миллиона случайных перестановок , эти 561 диффузные те имели . пар неисправны. Ds(P)306118/(5612)=6118/1570803.9%
hftf
1
@Raphael (# 3b) Из 10 миллионов случайных пар перестановок 306893 пары были невменяемыми. Только 29 из этих пар имели обе перестановки с . Вот гистограмма ( значения ). Ds(P)50
hftf

Ответы:

3

Один из подходов: вы можете свести это к следующей проблеме: учитывая булеву формулу , выберите равномерно случайное назначение из всех удовлетворяющих назначений . Эта проблема NP-сложна, но существуют стандартные алгоритмы для генерации который приблизительно равномерно распределен, заимствуя методы из алгоритмов #SAT. Например, одна из техник состоит в том, чтобы выбрать хэш-функцию , диапазон которой имеет тщательно выбранный размер (примерно такой же, как число удовлетворяющих присваиваний ), случайным образом выбрать случайным образом значение из диапазонаφ(x)xφ(x)xhφyh, а затем используйте SAT-решатель, чтобы найти удовлетворительное назначение для формулы . Чтобы сделать его эффективным, вы можете выбрать как разреженную линейную карту.φ(x)(h(x)=y)h

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

DW
источник
найти это трудно следовать. - логическое значение, а h ( x ) - двоичная строка (набор двоичных переменных)? итоговое уравнение означает ...? φ(x)h(x)
vzn
0

некоторое расширенное обсуждение / анализ этой проблемы началось в чате 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)).

статистика выводится для отклонений свыше c1000 отклонений по 3 подходам (# 116) и c= 1000 переключений (# 97), рассматривая 2 дисперсных алгоритма для неисправной пары от отклонения (# 19, # 106). последний отслеживает общую среднюю дисперсию (после гарантированного расстройства). пример выполнения выглядит следующим образом

c       0.661000
b       0.824000
a       0.927000
[2.484, 2, 4]
[2.668, 2, 4]

это показывает, что a-trueалгоритм дает наилучшие результаты с ~ 92% неотрицания и средним наихудшим дисперсионным расстоянием ~ 2,6, и гарантированным минимумом 2 на 1000 испытаний, то есть по крайней мере 1 неравный промежуточный элемент между всеми парами одинаковых элементов. он нашел решения до 3 неравных промежуточных элементов.

алгоритм отклонения - линейное предварительное отклонение по времени, а алгоритм дисперсии (работающий на нечувствительном входе), возможно, имеет значение ~ .O(nlogn)

1 проблема состоит в том, чтобы найти схемы пакетов викторины, которые удовлетворяют так называемому "фен шуй" [1] или "хорошему" случайному порядку, где "хороший" является несколько субъективным и еще не "официально" определенным количественно; автор проблемы проанализировал / свел ее к критериям отклонения / дисперсии, основанным на исследованиях сообщества викторин и «экспертов по фэн-шуй». [2] Есть разные идеи о «правилах фэн-шуй». Некоторое «опубликованное» исследование было сделано на алгоритмах, но оно появляется на ранних стадиях. [3]

[1] Пакет фэн-шуй / QBWiki

[2] Пакеты для викторины и фэн-шуй / Лифшиц

[3] Вопрос размещения , форум ресурсного центра HSQuizbowl

[4] Генерация случайных расстройств / Мартинес, Панхольцер, Продингер

[5] Алгоритм безумного ума (python) / McAndrew

ВЗН
источник
К тому же, подумал он, в сумасшедшей рутине есть сбой, и он не всегда сходит с ума. позиция обмена может продвигаться, ничего не меняя. Theres простое исправление, чтобы проверить успех правильно.
ВЗН