bug#80658: questions about "shuf" utility

On 2026-03-22 16:52, Terence Kelly wrote:

> 1. Can you confirm that shuf uses the Fisher-Yates/Durstenfeld unbiased 
> shuffle algorithm?

Never heard of that name for that algorithm, which I consider obvious. 
As I recall, I independently invented a superset of it in 2006 and shuf 
uses this superset algorithm, which is equivalent to 
Fisher-Yates/Durstenfeld in the special case you're surely thinking of. 
See coreutils/gl/lib/randperm.c's randperm_new.


> 2. Can you confirm that shuf avoids modulo bias --- the infamous and 
> widespread bug, "random_number%N" --- when it makes equiprobable 
> selections in its implementation of the shuffle algorithm?

Yes. See coreutils/gl/lib/randint.c's randint_genmax.


> 3. Can you confirm that when shuf's "--random-source=FILE" option is 
> used, the specified file is the sole source of random bits for all of 
> shuf's behavior, and that if the same random source file is used again, 
> holding all other shuf options & inputs constant, then shuf will emit 
> the same output?

Yes. See coreutils/gl/lib/randread.c's randread_new and its callers.


> Before I can recommend shuf, however, I must confirm that it is free of several defects that are often found in other random permutation software.

I suggest recommending coreutils 9.6 (2025-01-17) or later, due to the 
bug fixed here (a bug that's not on your list...):

https://cgit.git.savannah.gnu.org/cgit/coreutils.git/commit/?id=bfbb3ec7f798b179d7fa7b42673e068b18048899

The bug doesn't matter if you use --random-source=FILE, as that option 
bypasses the bug.