Есть ли алгоритм «сортировки», который возвращает случайную перестановку при использовании компаратора с переворотом?

9

Вдохновленный этим вопросом, в котором спрашивающий хочет знать, изменяется ли время выполнения, когда компаратор, используемый в стандартном алгоритме поиска, заменяется честным броском монеты, а также заметной неудачей Microsoft в написании генератора равномерной перестановки, мой вопрос, таким образом, таков: :

Существует ли алгоритм сортировки на основе сравнения, который в зависимости от нашей реализации компаратора будет:

  1. возвращать элементы в отсортированном порядке при использовании истинного компаратора (то есть сравнение делает то, что мы ожидаем в стандартном алгоритме сортировки)
  2. возвращать равномерно случайную перестановку элементов, когда компаратор заменяется честным подбрасыванием монеты (то есть возвращение x < y = trueс вероятностью 1/2, независимо от значений x и y)

Код для алгоритма сортировки должен быть таким же. Только код внутри «черного ящика» сравнения может быть изменен.

Джо
источник
Смотрите также этот вопрос .
Рафаэль
2
Смотрите также следующий интересный вопрос: cstheory.stackexchange.com/questions/5321/… .
Юваль Фильмус
1
Вы хотите, чтобы ваш случайный компаратор вел себя хорошо? Вот два возможных способа. (1) Как только компаратор решит, что , то x < y всегда, а также y > x . (2) То же самое, но, кроме того, если компаратор решит, что x < y и y < z , то он фиксирует x < zz > x ). В обоих случаях каждый необусловленный запрос все еще является полностью случайным. Икс<YИкс<YY>ИксИкс<Yy<zx<zz>x
Юваль Фильмус
@YuvalFilmus Я хочу, по сути, то, что запрашивается в вашем связанном вопросе, за исключением того, что та же схема должна также сортироваться, если мы заменим случайный вентиль вентилем сравнения-обмена, который упорядочивает пару элементов.
Джо
1
Смотрите здесь для хороших визуализаций.
Рафаэль

Ответы:

3

Следующий детерминированный (без компаратора) алгоритм работает для входного кортежа :(a1,,an)

  1. Выполните Fisher-Yates перемешайте с помощью компаратора с некоторой статической парой (скажем , ) в качестве подбрасывания монеты (делают выборку приемо-отказ). Если компаратор выдает 1 в первый раз, используйте его инвертированным, чтобы избежать бесконечного цикла отклонения в детерминированном случае.a1<a21
  2. (необязательное ускорение: попробуйте одну пару раз, где n - длина или ваш вход. Если какие-либо два выходных сигнала отличаются, возвращают перестановку, полученную в (1))nn
  3. Сортируйте массив, используя сортировку слиянием.

При наличии детерминированного отношения порядка в качестве компаратора этот алгоритм сортирует массив за время поскольку перемешивание Фишера-Йейтса выполняется в O ( n ) с использованием максимального O ( log n).О(NжурналN)О(N)случайная ) неслучайных «случайных битов» (например, вызовов вашего компаратора) ) в каждом шаге сортировка слиянием имеет одинаковую асимптотическую сложность. Результат (1) в этом случае совершенно бесполезен, но поскольку за ним следует реальная сортировка, это не вредит.О(журналN)

Учитывая реальный бросок монеты, когда компаратор (1) переставляет массив с равной вероятностью для каждой перестановки, и если вам действительно нужно сделать (3) (вы пропустили (2) или (2) не смогли определить случайность), это не вред, потому что распределение его результата зависит только от порядка его ввода, который равномерно распределен среди всех перестановок из-за (1), поэтому результат всего алгоритма также равномерно распределен. Количество раз, которое каждая повторная выборка-приемка должна быть геометрически распределена (отклонение с вероятностью ) и, следовательно, имеет ожидаемое значение<2. Каждоеиспользует повторение в большинствелогапбит, поэтому анализ выполнения почти такие жекакв детерминированном случае, но мы получить толькоожидаемое время работыотO(павторизуйтесьп), с возможностью nontermination (только прекращает<12<2журналNО(NжурналN) почти наверное ).


Как Джо отметил: Если вам не нравится , тест на первый бит в (1), делать (3) , затем (1) и использовать , который всегда 0 , так как массив уже отсортирован в детерминированный случай. Кроме того, вы должны вычесть ваше случайное число из верхней границы диапазона в цикле, потому что верхняя граница для случайного числа дает идентичную перестановку. Но имейте в виду, что (2) тогда запрещено, потому что вы всегда должны делать случайные действия в случае выкупа.an<a10


Вы даже можете использовать те же вызовы для вашего компаратора для (1) и (3), но затем доказать, что результат распределен равномерно, как минимум, намного сложнее, если вообще возможно.


Следующий алгоритм не имеет отдельных фаз для перемешивания и сортировки, но асимптотически медленнее. Это по сути вставка сортировки с бинарным поиском . Я буду использовать для обозначения ввода, а b k = ( b k , 1 , , b k , k ) для обозначения результата после k-го раунда:aзнак равно(a1,...,aN)bk=(bk,1,,bk,k)k

  1. Установите b1,1=a1
  2. Если то b 2 = ( a 2 , a 1 ) и ( c , d ) : = ( 2 , 1 ), иначе b 2 = ( a 1 , a 2 ) и ( c , d ) : = ( 1 , 2 ) . В любом случае a d <a2<a1b2=(a2,a1)(c,d):=(2,1)b2=(a1,a2)(c,d):=(1,2) всегда будет 0 (т. е. false) для неслучайного компаратора.ad<ac0
  3. Чтобы получить при k 3, сначала получим b k - 1 .bkk3bk1
  4. Пусть и k = 2 l , т.е. k - наименьшая степень 2, не меньшая, чем k .l=log2kk=2lk2k
  5. Пусть . Для каждого j { 1 , , l } пусть i j = { i j - 1 + 2 l - j i j - 1 + 2 l - j > k - 1 a d < a c i j - 1 i j - 1 + 2 л -i0=0j{1,,l}
    ij={ij1+2ljij1+2lj>k1ad<acij1ij1+2lj>k1¬(ad<ac)ij1+2ljij1+2ljk1bk1,ij1+2lj<akij1ij1+2ljk1¬(bk1,ij1+2lj<ak)
  6. Если повторите (5.) иначе b k = ( b k - 1 , 1 , , b k - 1 , i l - 1 , a k , b k - 1 , i l , , b k - 1 , к - 1 )il>kbk=(bk1,1,,bk1,il1,ak,bk1,il,,bk1,k1)
  7. Выход bn

Случайный случай: 5 + условие if из 6 - это, по сути, выборка принятия-отклонения. Остальная часть алгоритма - наивный случайный порядок: перемешайте первые элементов и добавьте kk1k элемент в каждую позицию с равной вероятностью. Если бы мы использовали обычную сортировку вставкой, мы бы получили вместо этого биномиальное распределение.

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

frafl
источник
@ Джо, можешь ли ты поместить все свои баллы, все еще действительные для поста в текущей форме, в один комментарий и удалить остальные?
frafl
Я надеялся на алгоритм, который не делает разные шаги в зависимости от того, какой компаратор используется. Можете ли вы избежать бесконечной петли отклонения, не исследуя компаратор? Я думаю, что вы могли бы избежать отказа, выполнив сначала шаг (3) ...
Джо
i
Первый комментарий: обратите внимание, что я не выбрасываю первый бит сэмпла, это «двойное использование». Я думал об инвертировании каждого второго бита, но это не помешало бы бесконечному циклу. На самом деле нужен какой-то нерегулярный шаблон, и он может отклонить гораздо больше записей. Конечно, я мог бы сделать XOR двумя самыми последними битами вместо первого и самого последнего, но это не сильно отличается.
2013 г.
ian<a10
4

n2A/2B1/n!n>21/n!A/2B

Юваль Фильмус
источник
1
Но это справедливо только в том случае, если нам нужна детерминированная граница времени выполнения, которая не была запрошена в этом вопросе. Если мы только требуем, чтобы ожидаемое время выполнения было конечным, это не должно быть проблемой.
frafl
1
Вам известен какой-нибудь разумный алгоритм сортировки, который не заканчивается за полиномиальное время?
Юваль Фильмус
2
Вы смешиваете детерминированный и случайный случай. Алгоритм может завершаться в детерминированное полиномное время, если вызывается с помощью детерминированного отношения порядка, и в ожидаемое полиномиальное время, если вызывается с монетой в качестве компаратора.
frafl
2k
kA/2k