Ответ 1
Общее замечание
Мой личный подход к правильности алгоритмов с вероятностью: если вы знаете, как доказать это правильно, то это, вероятно, правильно; если вы этого не сделаете, это, безусловно, неправильно.
Говоря иначе, обычно безнадежно пытаться проанализировать каждый алгоритм, который вы могли бы придумать: вам нужно продолжать поиск алгоритма, пока не найдете тот, который вы можете доказать правильно.
Анализ случайного алгоритма путем вычисления распределения
Я знаю об одном способе "автоматически" анализировать случайный выбор (или, скорее, алгоритм случайного использования), который сильнее, чем простой "бросать много тестов и проверять однородность". Вы можете механически вычислить распределение, связанное с каждым входом вашего алгоритма.
Общая идея заключается в том, что алгоритм случайного использования исследует часть мира возможностей. Каждый раз, когда ваш алгоритм запрашивает случайный элемент в наборе ({ true, false} при переворачивании монеты), для вашего алгоритма есть два возможных результата, и один из них выбран. Вы можете изменить свой алгоритм так, чтобы вместо того, чтобы возвращать один из возможных результатов, он исследует все решения параллельно и возвращает все возможные результаты с соответствующими дистрибутивами.
В общем, для этого потребуется переписать ваш алгоритм в глубину. Если ваш язык поддерживает разграниченные продолжения, вам не нужно; вы можете реализовать "исследование всех возможных результатов" внутри функции, запрашивающей случайный элемент (идея состоит в том, что случайный генератор вместо того, чтобы возвращать результат, фиксирует продолжение, связанное с вашей программой, и запускает его со всеми разными результатами). Пример такого подхода см. В разделе oleg HANSEI.
Промежуточное и, возможно, менее загадочное решение состоит в том, чтобы представить этот "мир возможных исходов" в качестве монады и использовать такой язык, как Haskell с возможностями для монадического программирования. Ниже приведен пример реализации варианта 1 вашего алгоритма в Haskell с использованием вероятностной монады пакета probability:
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 из-за конкретной обработки поворота. Если я не использую ни одного стержня, как в вашем случае, размер ввода не уменьшается на каждом шаге больше: в алгоритме также рассматривается случай, когда все входы находятся в левом списке (или в правом списке) и теряются в бесконечном цикле, Это слабость реализации вероятности монады (если алгоритм имеет вероятность 0 без прерывания, расчёт распределения может все еще расходиться), что я еще не знаю, как исправить.
Перетасовка по типу
Вот простой алгоритм, который я уверен, что могу доказать правильность:
- Выберите случайный ключ для каждого элемента вашей коллекции.
- Если ключи не все различны, перезапустите с шага 1.
- Сортировка коллекции по этим случайным клавишам.
Вы можете опустить шаг 2, если знаете вероятность столкновения (два случайных числа выбраны равными) достаточно низки, но без него тасовка не является совершенно однородной.
Если вы выбрали свои ключи в [1..N], где N - длина вашей коллекции, у вас будет много столкновений (проблема с днем рождения). Если вы выбираете свой ключ как 32-битное целое число, вероятность конфликта на практике низкая, но все еще зависит от проблемы с днем рождения.
Если вы используете бесконечные (лениво оцениваемые) битовые строки как ключи, а не ключи с конечной длиной, вероятность столкновения становится равной 0, и проверка отличимости больше не нужна.
Вот реализация shuffle в 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 вы знаете первый элемент каждого списка и т.д. Когда ваш алгоритм возвращается, список тестов полностью известен и элементы сортируются в соответствии с этими списками (отсортированы в лексикографическом порядке или рассматриваются как двоичные представления действительных чисел).
Итак, ваш алгоритм эквивалентен сортировке с помощью бесконечных клавиш битстрима. Действие разбиения списка, напоминающее секцию quicksort над сводным элементом, на самом деле является способом разделения для данной позиции в битовой строке элементов с оценкой 0 от элементов с оценкой 1.
Сорт является единообразным, потому что битстроны все разные. Действительно, два элемента с вещественными числами, равными до n -th бит, находятся на одной стороне раздела, возникающего во время рекурсивного вызова shuffle глубины n. Алгоритм завершается только тогда, когда все списки, являющиеся результатом разделов, пустыми или одиночными: все элементы разделены хотя бы одним тестом и поэтому имеют один отдельный двоичный десятичный знак.
Вероятностное окончание
Тонкая точка вашего алгоритма (или моего эквивалентного метода сортировки) заключается в том, что условие завершения является вероятностным. Fisher-Yates всегда заканчивается после известного количества шагов (количество элементов в массиве). С вашим алгоритмом окончание зависит от выхода генератора случайных чисел.
Возможны выходы, которые заставили бы ваш алгоритм расходиться, а не заканчиваться. Например, если генератор случайных чисел всегда выводит 0, каждый вызов partition будет возвращать список ввода без изменений, на котором вы рекурсивно вызываете перетасовку: вы будете бесконечно зацикливаться.
Однако это не проблема, если вы уверены, что ваш генератор случайных чисел справедлив: он не обманывает и всегда возвращает независимые равномерно распределенные результаты. В этом случае вероятность того, что тест random:uniform() < 0.5 всегда возвращает true (или false), точно равна 0:
- вероятность того, что первые N вызовов возвращаются
trueравна 2 ^ {- N} - вероятность того, что все вызовы возвращаются
true, - это вероятность бесконечного пересечения для всех N событий, которые первые N вызывает return0; это нижний предел ¹ 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 ленивых потоков различны, и что вероятность намного большего времени работы экспоненциально уменьшаться.