JUS*_*ION 76 algorithm functional-programming shuffle
就像背景一样,我知道Fisher-Yates完美的洗牌.它的O(n)复杂性和保证的一致性是一个很好的混乱,我不会使用它...在一个允许就地更新数组的环境中(所以在大多数情况下,如果不是全部,命令式编程环境).
可悲的是,函数式编程世界并没有让你访问可变状态.
然而,由于Fisher-Yates,我没有很多关于如何设计改组算法的文献.完全解决这个问题的几个地方之前做了这么简单的说法,实际上,"所以这里是Fisher-Yates,这是你需要知道的所有洗牌".最后,我必须提出自己的解决方案.
我想出的解决方案是这样的,可以随机播放任何数据列表:
在Erlang代码中,它看起来像这样:
shuffle([]) -> [];
shuffle([L]) -> [L];
shuffle(L) ->
{Left, Right} = lists:partition(fun(_) ->
random:uniform() < 0.5
end, L),
shuffle(Left) ++ shuffle(Right).
(如果这看起来像是一种疯狂的快速排序,那么,基本上就是这就是它.)
所以这就是我的问题:同样的情况使得找到非Fisher-Yates 的改组算法变得困难,这使得找到分析混洗算法的工具同样困难.在分析PRNG的均匀性,周期性等方面,我可以找到很多文献,但没有关于如何分析洗牌的大量信息.(事实上,我在分析shuffle时发现的一些信息是完全错误的 - 很容易通过简单的技术欺骗.)
所以我的问题是:我如何分析我的改组算法(假设那里的random:uniform()调用可以生成具有良好特性的适当随机数)？我可以使用哪些数学工具来判断,在1 ... 100的整数列表中,是否有100,000次洗牌运行给了我合理的改组结果？我已经做了一些我自己的测试(例如,比较增量到shuffles中的减量),但我想知道更多.
如果对该混洗算法本身有任何了解,也会受到重视.
gas*_*che 74
关于概率使用算法正确性的个人方法:如果你知道如何证明它是正确的,那么它可能是正确的; 如果你不这样做,那肯定是错的.
换句话说,尝试分析您可能提出的每个算法通常是没有希望的:您必须继续寻找算法,直到找到一个可以证明正确的算法.
我知道有一种方法可以"自动"分析一个比简单的"大量测试和检查均匀性"更强大的混洗(或更普遍的随机使用算法).您可以机械地计算与算法的每个输入相关联的分布.
一般的想法是随机使用算法探索可能性世界的一部分.每当您的算法要求集合中的随机元素({ true,false}翻转硬币时),您的算法有两种可能的结果,其中一种是选择的.您可以更改算法,以便不是返回其中一个可能的结果,而是并行探索所有解决方案并使用关联的分布返回所有可能的结果.
通常,这需要深入重写您的算法.如果您的语言支持分隔延续,则不必; 你可以在函数中实现"探索所有可能的结果",要求一个随机元素(这个想法是随机生成器,而不是返回一个结果,捕获与你的程序相关的延续,并用所有不同的结果运行它).有关此方法的示例,请参阅oleg的HANSEI.
一个中间人,可能不那么神秘的解决方案是将这个"可能结果的世界"表示为一个monad,并使用像Haskell这样的语言和monadic编程设施.下面是使用概率包的概率monad在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实现的变体.如果我不使用枢轴,就像你的情况一样,输入大小不再在每一步减少:算法也考虑所有输入都在左侧列表(或右侧列表)中的情况,并在无限循环中丢失.这是概率monad实现的弱点(如果算法具有非终止概率0,分布计算可能仍然分歧),我还不知道如何修复.
这是一个简单的算法,我相信我可以证明是正确的:
如果你知道碰撞的概率(两个随机数相等)足够低,你可以省略步骤2,但没有它,洗牌不是完全一致的.
如果你在[1..N]中选择你的钥匙,其中N是你的收藏的长度,你会有很多碰撞(生日问题).如果您将密钥选为32位整数,则实际上冲突的可能性很低,但仍然存在生日问题.
如果使用无限(懒惰评估)位串作为键而不是有限长度键,则碰撞的概率变为0,并且不再需要检查清晰度.
这是OCaml中的一个shuffle实现,使用惰性实数作为无限位串:
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 基于 mergesort的解决方案.
算法考虑因素:先前算法的复杂性取决于所有密钥是不同的概率.如果将它们选为32位整数,则特定键与另一个键碰撞的概率为〜40亿.这些键的排序是O(n log n),假设选择一个随机数是O(1).
如果你有无限的位串,你就不必重新开始挑选,但是复杂性与"平均评估流的元素数量"有关.我猜想它平均为O(log n)(因此总共仍为O(n log n)),但没有证明.
经过更多的反思,我认为(比如douplep),你的实现是正确的.这是一个非正式的解释.
列表中的每个元素都经过多次random:uniform() < 0.5测试.对于元素,您可以将这些测试的结果列表关联为布尔值列表或{ 0,1}.在算法开始时,您不知道与任何这些数字相关联的列表.第一后partition调用,你知道每个列表等.当你的算法返回,测试列表是完全已知和元素的第一个元素进行排序,根据这些名单(排序的字母排序,或者被认为是真正的二进制表示号).
因此,您的算法相当于按无限位串键排序.对列表进行分区的动作,让人联想到快速分配对枢轴元素的分区,实际上是一种分离位串中给定位置的元素,具有0来自具有估值的元素的估值1.
排序是统一的,因为位串都是不同的.实际上,具有与n第-th位相等的实数的两个元素在递归shuffle调用深度期间出现在分区的同一侧n.该算法仅在分区产生的所有列表为空或单例时终止:所有元素至少由一个测试分隔,因此具有一个不同的二进制十进制.
关于算法(或我的等效排序方法)的一个细微之处在于终止条件是概率性的.Fisher-Yates总是在已知步数(阵列中的元素数量)之后终止.使用您的算法,终止取决于随机数生成器的输出.
有可能的输出会使您的算法发散,而不是终止.例如,如果随机数生成器始终输出0,则每次partition调用都将返回输入列表不变,您将递归调用shuffle:您将无限循环.
但是,如果您确信您的随机数生成器是公平的,那么这不是问题:它不会作弊并始终返回独立的均匀分布结果.在这种情况下,测试random:uniform() < 0.5总是返回true(或false)的概率正好为0:
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终止.这是Fisher-Yates算法的略微保证,它始终终止.特别是,你很容易受到一个邪恶对手的攻击,它可以控制你的随机数发生器.
使用更多概率理论,您还可以计算给定输入长度的算法运行时间分布.这超出了我的技术能力,但我认为它很好:我认为你只需要平均看一下O(log N)的第一个数字来检查所有N个懒惰流是否不同,以及运行时间高得多的可能性以指数方式减少.
Pi *_*ort 22
您的算法是基于排序的混洗,如维基百科文章中所述.
一般来说,基于排序洗牌的计算复杂度是一样的底层的排序算法(例如O(ñ日志ñ)平均值,O(ñ ²)最坏的情况下为基于快速排序洗牌),和而分布不完全均匀,它应接近均匀,足以满足大多数实际需要.
Oleg Kiselyov提供以下文章/讨论:
涵盖基于排序洗牌的局限性,更详细,并且还提供了费-耶茨战略的两个调整:一个天真的O(ñ ²)之一,基于二叉树O(ñ日志ñ)之一.
可悲的是,函数式编程世界并没有让你访问可变状态.
事实并非如此:虽然纯函数式编程避免了副作用,但它支持使用一流效果访问可变状态,而不需要副作用.
在这种情况下,您可以使用Haskell的可变数组来实现本教程中描述的变异Fischer-Yates算法:
你的shuffle排序的具体基础实际上是一个无限关键的基数排序:正如gasche指出的那样,每个分区对应一个数字分组.
这个的主要缺点与任何其他无限键排序shuffle相同:没有终止保证.虽然终止的可能性随着比较的进行而增加,但是从来没有上限:最坏情况的复杂度是O(∞).