Общее замечание
Мой личный подход к правильности алгоритмов, использующих вероятность: если вы знаете, как доказать , это правильно, то, вероятно, это правильно;если вы этого не сделаете, это, безусловно, неправильно.
Иными словами, как правило, безнадежно пытаться проанализировать каждый алгоритм, который вы можете придумать: вы должны продолжать искать алгоритм, пока не найдете тот, который вам может оказаться верным.
Анализ случайного алгоритма путем вычисления распределения
Я знаю один способ "автоматического" анализа случайного числа (или, в более общем случае, алгоритма случайного использования)это сильнее, чем просто «бросить много тестов и проверить на однородность».Вы можете механически вычислить распределение, связанное с каждым входом вашего алгоритма.
Общая идея состоит в том, что алгоритм случайного использования исследует часть мира возможностей.Каждый раз, когда ваш алгоритм запрашивает случайный элемент в наборе ({true, false} при подбрасывании монеты), у вашего алгоритма есть два возможных результата, и выбирается один из них.Вы можете изменить свой алгоритм так, чтобы вместо возврата одного из возможных результатов он параллельно анализировал всех решений и возвращал все возможные результаты с соответствующими распределениями.
В общем случае этотребуют переписать ваш алгоритм в глубину.Если ваш язык поддерживает продолжения с разделителями, это не обязательно;вы можете реализовать «исследование всех возможных результатов» внутри функции, запрашивающей случайный элемент (идея состоит в том, что генератор случайных чисел вместо возврата результата захватывает продолжение, связанное с вашей программой, и запускает его со всеми различными результатами).Пример такого подхода см. В статье HANSEI .
, разработанной Олегом. Посредник, и, возможно, менее загадочное решение, состоит в том, чтобы представить этот «мир возможных результатов» в виде монады и использовать язык.например, Haskell со средствами для монадического программирования.Вот пример реализации варианта¹ вашего алгоритма в Haskell с использованием монады вероятности пакета вероятность :
import Numeric.Probability.Distribution
shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
(left, right) <- partition li
sleft <- shuffleM left
sright <- shuffleM right
return (sleft ++ [pivot] ++ sright)
where partition [] = return ([], [])
partition (x:xs) = do
(left, right) <- partition xs
uniform [(x:left, right), (left, x:right)]
Вы можете запустить его для заданного ввода и получитьраспределение выхода:
*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
[([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]
Вы можете видеть, что этот алгоритм одинаков с входами размера 2, но неоднороден на входах размера 3.
Разница с тестом на основеПодход заключается в том, что мы можем получить абсолютную уверенность за конечное число шагов: он может быть довольно большим, поскольку он представляет собой исчерпывающее исследование мира возможных (но обычно меньше 2 ^ N, поскольку существуют факторизации схожих результатов), но если он возвращает неравномерное распределение, мы точно знаем, что алгоритм неверен.Конечно, если он возвращает равномерное распределение для [1..N] и 1 <= N <= 100, вы знаете только, что ваш алгоритм одинаков вплоть до списков размером 100;это все еще может быть неправильно.
¹: этот алгоритм является вариантом реализации вашего Erlang из-за специфической обработки сводных данных.Если я не использую pivot, как в вашем случае, размер ввода больше не уменьшается на каждом шаге: алгоритм также учитывает случай, когда все входы находятся в левом списке (или правом списке), и теряются в бесконечном цикле,Это слабость реализации монады вероятностей (если у алгоритма есть вероятность не прекращения 0, вычисление распределения может все еще расходиться), которое я пока не знаю, как исправить.
На основе сортировкиshuffles
Вот простой алгоритм, который, я уверен, мог бы оказаться правильным:
- Выберите случайный ключ для каждого элемента в вашей коллекции.
- Если ключине все различны, перезапустите с шага 1.
- Сортируйте коллекцию по этим случайным ключам.
Шаг 2 можно опустить, если вы знаете вероятность столкновения (два случайных числа)выбраны равны) достаточно низок, но без него перемешивание не идеально равномерно.
Если вы выберете ключи в [1..N], где N - длина вашей коллекции, у вас будет много коллизий ( День рождения ). Если вы выберете свой ключ как 32-разрядное целое число, вероятность конфликта на практике будет низкой, но все равно будет возникать проблема с днем рождения.
Если вы используете бесконечные (лениво оцениваемые) строки битов в качестве ключей, а не ключи конечной длины, вероятность коллизии становится равной 0, и проверка отличимости больше не требуется.
Вот случайная реализация в OCaml, использующая ленивые действительные числа в качестве бесконечных цепочек битов:
type 'a stream = Cons of 'a * 'a stream lazy_t
let rec real_number () =
Cons (Random.bool (), lazy (real_number ()))
let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
compare_real a' b'
let shuffle list =
List.map snd
(List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
(List.map (fun x -> real_number (), x) list))
Есть и другие подходы к "чистой перетасовке". Хорошим примером является решение на основе слияния от apfelmus .
Алгоритмические соображения: сложность предыдущего алгоритма зависит от вероятности того, что все ключи различны. Если вы выберете их как 32-разрядные целые числа, у вас есть вероятность в ~ 4 миллиарда, что определенный ключ сталкивается с другим ключом. Сортировка по этим ключам O (n log n), при условии выбора случайного числа O (1).
Если у вас бесконечные цепочки битов, вам никогда не придется перезапускать сбор, но сложность тогда связана с тем, «сколько элементов потоков оценивается в среднем». Я предполагаю, что это O (log n) в среднем (следовательно, O (n log n) в целом), но не имеет доказательств.
... и я думаю, что ваш алгоритм работает
После дополнительного размышления, я думаю (как douplep), что ваша реализация верна. Вот неофициальное объяснение.
Каждый элемент в вашем списке проверен несколькими random:uniform() < 0.5 тестами. Элементу можно связать список результатов этих тестов в виде списка логических значений или {0, 1}. В начале алгоритма вы не знаете список, связанный с каким-либо из этих чисел. После первого вызова partition вы знаете первый элемент каждого списка и т. Д. Когда ваш алгоритм возвращается, список тестов полностью известен, и элементы отсортированы в соответствии с этими списками (отсортированы в лексикографическом порядок или рассматривается как двоичные представления действительных чисел).
Итак, ваш алгоритм эквивалентен сортировке по бесконечным цепочкам ключей. Действие разделения списка, напоминающее разделение быстрой сортировки по элементу pivot, фактически является способом отделения для данной позиции в цепочке битов элементов с оценкой 0 от элементов с оценкой 1.
Сортировка однородна, потому что все цепочки битов разные. Действительно, два элемента с действительными числами, равными n -ому биту, находятся на одной стороне раздела, происходящего во время рекурсивного shuffle вызова глубины n. Алгоритм завершается только тогда, когда все списки, полученные из разделов, пусты или синглетны: все элементы были разделены по крайней мере одним тестом и, следовательно, имеют одно отличное двоичное десятичное число.
Вероятностное завершение
Тонкое замечание относительно вашего алгоритма (или моего эквивалентного метода на основе сортировки) состоит в том, что условие завершения вероятностное . Фишер-Йейтс всегда заканчивается после известного количества шагов (количество элементов в массиве). С вашим алгоритмом завершение зависит от выхода генератора случайных чисел.
Существуют возможные выходные данные, которые заставят ваш алгоритм расходиться , а не завершаться. Например, если генератор случайных чисел всегда выводит 0, каждый вызов partition будет возвращать список ввода без изменений, для которого вы рекурсивно вызываете случайное перемешивание: цикл будет бесконечным.
Однако, это не проблема, если вы уверены, что ваш генератор случайных чисел справедлив: он не обманывает и всегда возвращает независимые равномерно распределенные результаты. В этом случае вероятность того, что тест random:uniform() < 0.5 всегда вернет true (или false), равна 0:
- вероятность того, что первые N вызовов вернут
true, равна 2 ^ {- N} - вероятность того, что все вызовы вернутся
true - это вероятность бесконечного пересечения, для всех N, события, когда первые N вызовов вернутся 0; это нижний предел¹ 2 ^ {- N}, который равен 0
¹: математические детали см. http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets
В более общем смысле алгоритм не завершается тогда и только тогда, когда некоторые элементы связываются с одним и тем же логическим потоком. Это означает, что как минимум два элемента имеют одинаковый логический поток. Но вероятность того, что два случайных логических потока равны, снова равна 0: вероятность того, что цифры в позиции K равны, равна 1/2, поэтому вероятность того, что N первых цифр равны, равна 2 ^ {- N}, и то же самое анализ применим.
Следовательно, вы знаете, что ваш алгоритм завершается с вероятностью 1 . Это немного более слабая гарантия того, что алгоритм Фишера-Йейтса, который всегда завершается . В частности, вы уязвимы для атаки злого противника, который будет контролировать ваш генератор случайных чисел.
Имея больше теории вероятностей, вы также можете вычислить распределение времени выполнения вашего алгоритма для заданной входной длины. Это выходит за рамки моих технических возможностей, но я предполагаю, что это хорошо: я полагаю, что вам нужно только посмотреть на O (log N) первые цифры в среднем, чтобы проверить, что все N lazy потоков отличаются, и что вероятность намного более высокого времени выполнения экспоненциально.