相关疑难解决方法(0)

就像背景一样,我知道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中的减量),但我想知道更多.

如果对该混洗算法本身有任何了解,也会受到重视.

我有一个伪随机数生成器(PRNG)类,我想进行单元测试.有两种方法:

1. 编写一个测试用例,其中包含大量样本并测试它们是否正确分布.这种方法可能会导致测试用例的执行时间相当长;
2. 手动计算一小部分样本,并验证PRNG算法是否重现它.这种方法可能导致在不被注意的情况下生成非随机序列;

我会说第一种方法不是真正的单元测试,因为它不执行发生器的白盒测试,但另一方面它正确地测试了类的责任.第二种方法更像是一个真正的单元测试,侧重于算法,但它没有提供足够的证据来证明该类是否履行其职责.

您更喜欢哪种方法？为什么？

我需要一个以随机顺序返回数组的函数.我想确保它是随机的,但我不知道如何编写测试来确保数组真的是随机的.我可以多次运行代码,看看我是否多次使用相同的答案.虽然大型阵列不太可能发生碰撞,但很可能是小型阵列(比如说两个元素).

我该怎么办呢？

我现在正在为自己开展一个小项目,我正在利用它作为一个了解单元测试和维护适当文档的机会.

我有一个Deck代表一副牌的课(这很简单,说实话,我可以肯定它没有单元测试,但就像我说我已经习惯了使用单元测试)它有一个shuffle() 改变卡片中卡片顺序的方法.

实现非常简单,肯定会起作用:

public void shuffle()
{
    Collections.shuffle(this.cards);
}

但是,我怎么能为这个方法实现单元测试.我的第一个想法是在通话后检查牌组的顶牌是否有所不同,shuffle()但当然有可能是相同的.我的第二个想法是检查整个卡的顺序是否已经改变,但它们可能也是相同的顺序.那么,我怎么能编写一个测试来确保这种方法适用于所有情况呢？而且,一般来说,如何对结果取决于某些随机性的单元测试方法进行单元化？

干杯,

皮特

不久前我在接受采访时,需要解决两个非常有趣的问题.我很好奇你会如何处理这些解决方案.

问题1:

除了当前的一切产品

编写一个函数,将两个长度为len,input和index的整数数组作为输入,并生成第三个数组result,结果如下:result [i] =输入中除输入[index [i]]之外的所有内容的乘积

例如,如果使用len = 4,input = {2,3,4,5}和index = {1,3,2,0}调用该函数,则结果将设置为{40,24,30 ,60}.

重要信息:您的算法必须以线性时间运行.

问题2 :(主题在Jeff帖子中)

洗牌卡甲板均匀

1. 设计(在C++或C#中)一个类Deck代表一张有序的牌组,其中牌组包含52张牌,分为13个等级(A,2,3,4,5,6,7,8,9, 4,J,Q,K)四件套装:黑桃(？),心形(？),钻石(？)和球杆(？).

2. 基于这个类,设计和实现一个有效的算法来洗牌一副牌.牌必须均匀洗牌,也就是说,原牌中的每张牌必须具有相同的概率才能最终进入洗牌牌的任何可能位置.该算法应该在Deck类的方法shuffle()中实现:void shuffle()

3. 算法的复杂程度是多少(作为卡片中卡片数量n的函数)？

4. 解释如何测试您的方法均匀地洗牌(黑盒测试).

PS我有两个小时来编写解决方案代码