Re：随机排序一个集合 [英] Re: random sorting a collection
问题描述
2008年5月28日星期三06:23:35 -0700，Adam Sandler< co **** @ excite.comwrote：
On Wed, 28 May 2008 06:23:35 -0700, Adam Sandler <co****@excite.comwrote:
[.. 。]
问题是，排序后的数组现在可以包含重复数据！
[...]
The problem is, the sorted array can now contain duplicates!
不，它不可能。除非它有重复开头。
就个人而言，我不会为这样一个人为的循环而烦恼。东西
更简单很好：
for（int i = 0; i< a.Length; i ++）
{
int j = r.Next（a.Length）;
String temp = a [i];
a [i ] = a [j];
a [j] = temp;
}
然后你避免所有-1和+1并且一个接一个。对于
洗牌输入的目的，你可能会改变你已经洗牌过的物品并不重要。它仍然是随机的。
如果你问我，你引用的整个帖子有点粗略。
Pete
推荐答案
5月28日下午3:39，Peter Duniho < NpOeStPe ... @nnowslpianmk.com>
写道：
< snip>
On May 28, 3:39 pm, "Peter Duniho" <NpOeStPe...@nnowslpianmk.com>
wrote:
<snip>
然后你避免所有的-1和+1以及一个一个。对于
洗牌输入的目的，你可能会改变你已经洗牌过的物品并不重要。它仍然是随机的。
Then you avoid all the -1 and +1 and off-by-one. For the purposes of
shuffling the input, it doesn''t matter that you might shuffle an item that
you''d already shuffled. It''s still random.
但最终会减少随机性。与真正的洗牌，IIRC相比，某些东西最终会落到初始位置的可能性更小。它需要一点* *的工作来消除掉一个错误，但是
它并没有那么糟糕。
我个人把它写成：
// i =我们要替换的位置（可能使用相同的元素）
//比我更少的东西已经洗牌了
for（int i = 0; i< a.Length; i ++）
{
//目标在范围内[i，a.Length]
int target = i + rng.Next（a.Length-i）;
String temp = a [i];
a [i] = a [target];
a [target] = temp;
}
Jon
It ends up being less random though. It''s less likely that something
will end up in its initial position than with a true shuffle, IIRC. It
takes a *little* more work to get rid of the off-by-one errors, but
it''s not that bad.
I''d personally write it as:
// i=position we''re going to replace (possibly with same element)
// Everything less than i is already shuffled
for (int i=0; i < a.Length; i++)
{
// target is in range [i, a.Length)
int target = i+rng.Next(a.Length-i);
String temp = a[i];
a[i] = a[target];
a[target] = temp;
}
Jon
2008年5月28日星期三08:30:18 -0700，Jon Skeet [C＃MVP]< ; sk *** @ pobox.com>
写道：
On Wed, 28 May 2008 08:30:18 -0700, Jon Skeet [C# MVP] <sk***@pobox.com>
wrote:
5月28日下午3:39，Peter Duniho < NpOeStPe ... @nnowslpianmk.com>
写道：
< snip>
On May 28, 3:39 pm, "Peter Duniho" <NpOeStPe...@nnowslpianmk.com>
wrote:
<snip>
>然后你避免所有的-1和+1和一个一个。为了改变输入的目的，你可以随意洗牌
你已经洗牌过了没关系。它仍然是随机的。
>Then you avoid all the -1 and +1 and off-by-one. For the purposes of
shuffling the input, it doesn''t matter that you might shuffle an item
that
you''d already shuffled. It''s still random.
但最终会减少随机性。与真正的洗牌，IIRC相比，某些东西最终会落到初始位置的可能性更小。
It ends up being less random though. It''s less likely that something
will end up in its initial position than with a true shuffle, IIRC.
顺便说一句，我终于有机会尝试查找
会反驳或验证这一点的参考。我在维基百科中找到一个论点，指出
，对于一个shuffle，有N！排列，但是在每次迭代中从每个可能的索引中选择一个随机交换产生N ^ N
随机选择的可能结果。然后它指出N ^ N
永远不会被N整除！并使用它声称一些排列
必须更频繁地出现（基本上，可能的
随机结果中有重复，但仅限于某些排列）。
无论如何，这是一个很长的说法，我认为你是对的。
只要我评论，我'我会指出，如果我们要去修改算法以便产生正确的均匀分布，我们
也可以利用这个机会和减少我们的迭代次数
减一。因此，而不是：
By the way, I did finally get a chance to try to look up a reference that
would refute or verify this. I found in Wikipedia an argument that points
out that for a shuffle, there are N! permutations, but that selecting a
random swap from every possible index on each iteration produces N^N
possible outcomes for the random selections. It then points out that N^N
is never divisible by N! and uses that to claim that some permutations
must occur more often (basically, there are duplicates in the possible
random outcomes, but only for some permutations).
Anyway, that''s a long way of saying I think you''re right.
As long as I''m commenting, I''ll point out though that if we''re going to
fix the algorithm so that it produces correct uniform distribution, we
might as well take advantage of the chance and reduce our iteration count
by one. So instead of:
for（int i = 0; i< a.Length; i ++）
for (int i = 0; i < a.Length; i++)
我们可以：
we can have:
for（int i = 0; i< a.Length - 1; i ++）
for (int i = 0; i < a.Length - 1; i++)
不像你提出的那个好挑剔，但这都是我所得到的b $ b。 :)
关于不换东西的另一个优化
在同一个地方结束，但这涉及更多（相对来说）
说话）基本算法的复杂变化，因此更容易
有资格作为过早优化。上面我觉得它的简单性是有道理的，因为我会忽略可能更有益的优惠。
优化。我觉得整个思考过程有点反直觉和反讽。 :)
Pete
Not nearly as good a nitpick as the one you came up with, but it''s all
I''ve got. :)
There''s another optimization with respect to not swapping with something
winds up in the same place, but that involves a much more (relatively
speaking) complex change to the basic algorithm, and so more easily
qualifies as a premature optimization. The above I think makes sense due
to its simplicity, even as I would ignore the potentially more beneficial
optimization. I find this whole thought process somewhat
counter-intuitive and ironic. :)
Pete
这篇关于Re：随机排序一个集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
