How can I randomize (shuffle) the order of lines in a file? Or select a random line from a file, or select a random file from a directory?

To randomize the lines of a file, here is one approach. This one involves generating a random number, which is prefixed to each line; then sorting the resulting lines, and removing the numbers.

# Bash/Ksh
randomize() {
    while IFS='' read -r l ; do printf '%d\t%s\n' "$RANDOM" "$l"; done |
    sort -n |
    cut -f2-
}

RANDOM is supported by BASH and KornShell, but is not defined by POSIX.

Here's the same idea (printing random numbers in front of a line, and sorting the lines on that column) using other programs:

# Bourne
awk '
    BEGIN { srand() }
    { print rand() "\t" $0 }
' |
sort -n |    # Sort numerically on first (random number) column
cut -f2-     # Remove sorting column

This is (possibly) faster than the previous solution, but will not work for very old AWK implementations (try nawk, or gawk, or /usr/xpg4/bin/awk if available). (Note that AWK uses the epoch time as a seed for srand(), which may or may not be random enough for you.)

Other non-portable utilities that can shuffle/randomize a file:

Recent GNU sort has the -R (aka --random-sort) flag. Oddly enough, it only works for the generic locale:

LC_ALL=C sort -R file     # output the lines in file in random order
LC_ALL=POSIX sort -R file # output the lines in file in random order
LC_ALL=en_US sort -R file # effectively ignores the -R option

For more details, see info coreutils sort or an equivalent manual.

Shuffling an array

A generalized version of this question might be, How can I shuffle the elements of an array? If we don't want to use the rather clumsy approach of sorting lines, this is actually more complex than it appears. A naive approach would give us badly biased results. A more complex (and correct) algorithm looks like this:

# Uses a global array variable.  Must be compact (not a sparse array).
# Bash syntax.
shuffle() {
   local i tmp size max rand

   # $RANDOM % (i+1) is biased because of the limited range of $RANDOM
   # Compensate by using a range which is a multiple of the array size.
   size=${#array[*]}
   max=$(( 32768 / size * size ))

   for ((i=size-1; i>0; i--)); do
      while (( (rand=$RANDOM) >= max )); do :; done
      rand=$(( rand % (i+1) ))
      tmp=${array[i]} array[i]=${array[rand]} array[rand]=$tmp
   done
}

This function shuffles the elements of an array in-place using the Knuth-Fisher-Yates shuffle algorithm.

If we just want the unbiased random number picking function, we can split that out separately:

# Returns random number from 0 to ($1-1) in global var 'r'.
# Bash syntax.
rand() {
    local max=$((32768 / $1 * $1))
    while (( (r=$RANDOM) >= max )); do :; done
    r=$(( r % $1 ))
}

This rand function is better than using $((RANDOM % n)). For simplicity, many of the remaining examples on this page may use the modulus approach. In all such cases, switching to the use of the rand function will give better results; this improvement is left as an exercise for the reader.

Selecting a random line/file

Another question we frequently see is, How can I print a random line from a file? You do not need to know how many lines are in a file in order to choose a random one, however the solutions that do this are left intact below.

Without counting lines first

If you happen to have GNU shuf you can use that, but it is not portable.

# example, 5 random lines from file
shuf -n 5 file

If we want n random lines we need to:

  1. accept the first n lines
  2. accept each further line with probability n/nl where nl is the number of lines read so far
  3. if we accepted the line in step 2, replace a random one of the n lines we already have

# WARNING: srand() without an argument seeds using the current time accurate to the second. If run more than once in a single second on the clock you will get the same output. Find a better way to seed this.

n=$1
shift

awk -vn="$n" '
BEGIN            { srand()                           }
NR     <= n      { lines[NR - 1         ] = $0; next }
rand() <  n / NR { lines[int(rand() * n)] = $0       }
END              { for (k in lines) print lines[k]   }
' "$@"

Bash and POSIX sh solutions forthcoming.

With counting lines first

The problem here is that you need to know in advance how many lines the file contains. Lacking that knowledge, you have to read the entire file through once just to count them -- or, you have to suck the entire file into memory. Let's explore both of these approaches.

# Bash
n=$(wc -l <"$file")         # Count number of lines.
r=$((RANDOM % n + 1))       # Random number from 1..n (see warnings above!)
sed -n "$r{p;q;}" "$file"   # Print the r'th line.

# POSIX with (new) AWK
awk -v n="$(wc -l <"$file")" \
  'BEGIN{srand();l=int((rand()*n)+1)} NR==l{print;exit}' "$file"

(See FAQ 11 for more info about printing the r'th line.)

The next example sucks the entire file into memory. This approach saves time rereading the file, but obviously uses more memory. (Arguably: on systems with sufficient memory and an effective disk cache, you've read the file into memory by the earlier methods, unless there's insufficient memory to do so, in which case you shouldn't, QED.)

# Bash
unset lines n
while IFS= read -r 'lines[n++]'; do :; done < "$file"   # See FAQ 5
r=$((RANDOM % n))   # See warnings above!
echo "${lines[r]}"

Note that we don't add 1 to the random number in this example, because the array of lines is indexed counting from 0.

Also, some people want to choose a random file from a directory (for a signature on an e-mail, or to choose a random song to play, or a random image to display, etc.). A similar technique can be used:

# Bash
files=(*.ogg)                  # Or *.gif, or *
n=${#files[@]}                 # For readability
xmms -- "${files[RANDOM % n]}" # Choose a random element

Known bugs

Using external random data sources

Some people feel the shell's builtin RANDOM parameter is not sufficiently random for their applications. Typically this will be an interface to the C library's rand(3) function, although the Bash manual does not specify the implementation details. Some people feel their application requires cryptographically stronger random data, which would have to be supplied by some external source.

Before we explore this, we should point out that often people want to do this as a first step in writing some sort of random password generator. If that is your goal, you should at least consider using a password generator that has already been written, such as pwgen.

Now, if we're considering the use of external random data sources in a Bash script, we face several issues:

At this point you should be seriously rethinking your decision to do this in Bash. Other languages already have features that take care of all these issues for you, and you may be much better off writing your application in one of those languages instead.

You're still here? OK. Let's suppose we're going to use the /dev/urandom device (found on most Linux and BSD systems) as an external random data source in Bash. This is a character device which produces raw bytes of "pretty random" data. First, we'll note that the script will only work on systems where this is present. In fact, you should add an explicit check for this device somewhere early in the script, and abort if it's not found.

Now, how can we turn these bytes of data into numbers for Bash? If we attempt to read a byte into a variable, a NUL byte would give us a variable which appears to be empty. However, since no other input gives us that result, this may be acceptable -- an empty variable means we tried to read a NUL. We can work with this. The good news is we won't have to fork an od(1) or any other external program to read bytes. Then, since we're reading one byte at a time, this also means we don't have to write any prefetching or buffering code to save forks.

One other gotcha, however: reading bytes only works in the C locale. If we try this in en_US.utf8 we get an empty variable for every byte from 128 to 255, which is clearly no good.

So, let's put this all together and see what we've got:

   1 #!/usr/bin/env bash
   2 # Requires Bash 3.1 or higher, and an OS with /dev/urandom (Linux, BSD, etc.)
   3 
   4 export LANG=C
   5 if [[ ! -e /dev/urandom ]]; then
   6     echo "No /dev/urandom on this system" >&2
   7     exit 1
   8 fi
   9 
  10 # Return an unbiased random number from 0 to ($1 - 1) in variable 'r'.
  11 rand() {
  12     if (($1 > 256)); then
  13         echo "Argument larger than 256 currently unsupported" >&2
  14         r=-1
  15         return 1
  16     fi
  17 
  18     local max=$((256 / $1 * $1))
  19     while IFS= read -r -n1 -d '' r < /dev/urandom
  20           printf -v r %d "'$r"
  21           ((r >= max))
  22     do
  23         :
  24     done
  25     r=$((r % $1))
  26 }

This uses a trick from FAQ 71 for converting bytes to numbers. When the variable populated by read is empty (because of a NUL byte), we get 0, which is just what we want.

Extending this to handle ranges larger than 0..255 is left as an exercise for the reader.


CategoryShell

BashFAQ/026 (last edited 2014-05-01 17:52:24 by exit1)