[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 berni44 changed: What|Removed |Added Status|REOPENED|RESOLVED CC||bugzi...@d-ecke.de Resolution|--- |INVALID --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 Ivan Kazmenko changed: What|Removed |Added Status|RESOLVED|REOPENED CC||ga...@mail.ru Resolution|FIXED |--- --- Comment #2 from Ivan Kazmenko --- Looks like the documented behavior is wanted too: http://forum.dlang.org/thread/hqzijswbexlsaoecc...@forum.dlang.org 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. --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 Edwin van Leeuwen changed: What|Removed |Added CC||ed...@tkwsping.nl --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #3 from Joseph Rushton Wakeling --- (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. --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #4 from Ivan Kazmenko --- (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. --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #5 from Joseph Rushton Wakeling --- (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 :-) --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #6 from Ivan Kazmenko --- Here's my take at it: https://github.com/D-Programming-Language/phobos/pull/3302 --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #7 from github-bugzi...@puremagic.com --- Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/7329ef7eaee2e823ff73683b9032e7fd31971b2e reverted partialShuffle to match its documentation (issue 11738) https://github.com/D-Programming-Language/phobos/commit/ae6ec9c2bdaca78e626ae0feb5fc299e499d8b9c Merge pull request #3302 from GassaFM/issue_11738 reverted partialShuffle to match its documentation (issue 11738) --
[Issue 11738] partialShuffle actually shuffles the entire input
https://issues.dlang.org/show_bug.cgi?id=11738 --- Comment #8 from github-bugzi...@puremagic.com --- Commits pushed to dmd-cxx at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/7329ef7eaee2e823ff73683b9032e7fd31971b2e reverted partialShuffle to match its documentation (issue 11738) https://github.com/dlang/phobos/commit/ae6ec9c2bdaca78e626ae0feb5fc299e499d8b9c Merge pull request #3302 from GassaFM/issue_11738 --
[Issue 11738] partialShuffle actually shuffles the entire input
https://d.puremagic.com/issues/show_bug.cgi?id=11738 --- Comment #1 from github-bugzi...@puremagic.com 2013-12-15 15:24:13 PST --- Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/fbc8d1e08e122acb04306a21f73a3c5dd936a350 Fix Issue 11738 - partialShuffle should actually _be_ a partial shuffle :-) This patch fixes the problem that partialShuffle was in fact invariably shuffling the whole of the input, undetected because there were unittests only for randomShuffle. As well as the fix I've added some unittests specifically for partialShuffle to ensure that it works properly, and I've taken the opportunity to tweak a couple of bits of Ddoc and tidy up the randomShuffle unittests. https://github.com/D-Programming-Language/phobos/commit/277ce347e917747fb048b3933100a9bd8fd768fe Merge pull request #1773 from WebDrake/partial-shuffle Fix Issue 11738 - partialShuffle should actually _be_ a partial shuffle :-) -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 11738] partialShuffle actually shuffles the entire input
https://d.puremagic.com/issues/show_bug.cgi?id=11738 Joseph Rushton Wakeling changed: What|Removed |Added Status|NEW |RESOLVED Resolution||FIXED -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
