shuf: fix random line selection. Closes 9971
authorDenys Vlasenko <vda.linux@googlemail.com>
Sat, 8 Jul 2017 22:39:15 +0000 (00:39 +0200)
committerDenys Vlasenko <vda.linux@googlemail.com>
Fri, 4 Aug 2017 00:17:42 +0000 (02:17 +0200)
commit310bcec4dcfaeaf4afa40a5b03e588fd224aeda3
tree762447d2598dac871f7b9d39f705923499cf25a7
parent8fd69c7bdb217d1c5030dbc9cfdb0acb4205c6b7
shuf: fix random line selection. Closes 9971

"""
For example, given input file:

    foo
    bar
    baz

after shuffling the input file, foo will never end up back on the first line.
This came to light when I ran into a use-case where someone was selecting
a random line from a file using shuf | head -n 1, and the results on busybox
were showing a statistical anomaly (as in, the first line would never ever
be picked) vs the same process running on environments that had gnu coreutils
installed.

On line https://git.busybox.net/busybox/tree/coreutils/shuf.c#n56 it uses
r %= i, which will result in 0 <= r < i, while the algorithm specifies
0 <= r <= i.
"""

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
coreutils/shuf.c