[Issue 11738] partialShuffle actually shuffles the entire input

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=11738

Ivan Kazmenko <gassa at mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |gassa at mail.ru
         Resolution|FIXED                       |---

--- Comment #2 from Ivan Kazmenko <gassa at mail.ru> ---
Looks like the documented behavior is wanted too:
http://forum.dlang.org/thread/hqzijswbexlsaoeccozr@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.

--