Comment #0 by joseph.wakeling — 2013-12-14T02:30:43Z
Created attachment 1301
Test case to illustrate the bug.
partialShuffle(input, n) is supposed to shuffle input[0 .. n] and leave input[n
.. $] untouched. In fact it shuffles the entire input.
This is illustrated by the attached code, where the second half of the
partially shuffled array should still read 5, 6, 7, 8, 9 but is actually
randomly rearranged.
It's trivially fixable: on std/random.d:L1480 the second argument to uniform()
should be n - i, not r.length - i. A copy-paste error from an earlier
iteration of randomShuffle, perhaps? :-)
Comment #1 by github-bugzilla — 2013-12-15T15:24:13Z
Looks like the documented behavior is wanted too:
http://forum.dlang.org/thread/[email protected]
Suppose we have a random-access range of size M and want to pick N elements from it. In O(N), we can do two things:
1. Shuffle the first N elements. This is what the function now does:
partialShuffle ([0,1,2,3,4, 5,6,7,8,9], 5) can produce [4,0,2,3,1, 5,6,7,8,9].
2. Bring K random elements to the first N positions. This is what the documentation implies:
partialShuffle ([0,1,2,3,4, 5,6,7,8,9], 5) can produce [5,9,2,0,3, other elements in irrelevant order].
The benefit is that we select random N elements from M in O(N), not O(M). Other elements are still there at positions [N..M]. We can partialShuffle again with same or different N, and get another random bunch of elements at the front. The elements at positions [N..M] are neither sorted nor shuffled (some permutations have zero probability since we did only N swaps).
As pointed out in the D.learn thread linked above, the behavior (1) can already be obtained by slicing (like theArray[0..K] for an array, or perhaps theRange.take (K) for a range) and then fully (not partially) shuffling what we got.
On the other hand, the behavior (2) is not found in Phobos, at least after the fix.
So I think this fix was an error. I suggest we revert it, like
- swapAt(r, i, uniform(i, n, gen));
+ swapAt(r, i, uniform(i, r.length - i, gen));
Disclaimer: I may have misunderstood the issue, in which case, please explain what is the intent here.
Ivan Kazmenko.
Comment #3 by joseph.wakeling — 2015-05-20T21:43:30Z
(In reply to Ivan Kazmenko from comment #2)
> Disclaimer: I may have misunderstood the issue, in which case, please
> explain what is the intent here.
At first glance, I reckon it's my screw-up misinterpreting the documentation. Sorry about that. :-(
I'm not sure how much time I have in the near future, but I don't object to the original patch being reverted.
Comment #4 by gassa — 2015-05-20T21:47:31Z
(In reply to Joseph Rushton Wakeling from comment #3)
> (In reply to Ivan Kazmenko from comment #2)
> > Disclaimer: I may have misunderstood the issue, in which case, please
> > explain what is the intent here.
>
> At first glance, I reckon it's my screw-up misinterpreting the
> documentation. Sorry about that. :-(
>
> I'm not sure how much time I have in the near future, but I don't object to
> the original patch being reverted.
I can submit a PR for that ~tomorrow if you want, seems trivial: change one line of actual code and a few unittests.
Comment #5 by joseph.wakeling — 2015-05-20T22:37:03Z
(In reply to Ivan Kazmenko from comment #4)
> I can submit a PR for that ~tomorrow if you want, seems trivial: change one
> line of actual code and a few unittests.
Sounds great, thank you :-)