And then Nemo wanted weighted random numbers

Share

Nemo then wanted weighted random numbers, so this item has been added to this page. The following script selects a random element from a weight list of options…


#!/bin/bash

# Copyright (c) Michael Still 2002
# Released under the terms of the GNU GPL

# In this case, Nemo wants to be able to specify a list of items, with
# weights associated with them…

# $1 is the list with weights, in the form:
# “1 frog 2 banana 3 hamster”

# Scary assumption number one, people hand me correctly formatted lists
# Incidentally, this will break with numbers exist in the items I am handed
# e.g. Banana42 will break this
NUMBERS=`echo $1 | sed ‘s/[^0-9 ]//g’`
WORDS=`echo $1 | sed ‘s/[0-9]//g’`
WEIGHTED=””

# Build the list of options, including the weights
for NUM in $NUMBERS
do
WORD=`echo $WORDS | sed ‘s/ .*$//’`
WORDS=`echo $WORDS | sed “s/^$WORD *//”`

COUNT=0
while [ $COUNT -lt $NUM ]
do
WEIGHTED=`echo “$WEIGHTED $WORD”`
COUNT=$(( $COUNT + 1 ))
done
done

# Get the random number
LOBOUND=1
HIBOUND=`echo $WEIGHTED | wc -w`
RANDMAX=32767
BINUMBER=$(( $LOBOUND + ($HIBOUND * $RANDOM) / ($RANDMAX + 1) ))

# Get the item — I can’t use shift, because it is not on the command line
COUNT=1
while [ $COUNT -lt $BINUMBER ]
do
WEIGHTED=`echo $WEIGHTED | sed ‘s/^[^ ]*//’`
COUNT=$(( $COUNT + 1 ))
done

# The first word should be magic selected one
echo $WEIGHTED | sed ‘s/ .*$//’

Share

Getting an arbitary item from a list

Share

This script gets the specified element form the list on the command line…


#!/bin/bash

# Select a specified item from a list. Copyright (c) Michael Still 2002
# Released under the terms of the GNU GPL

# $1 is the number to get, $* except for $1 is the list of options, delimited
# by a space each

# We can the shift operation to get to the right number
shift $1
echo $1

Share

The challenge and the result

Share

So, I was at a CLUG meeting last night, and one of the speakers had a whole bunch of bash scripts for XDM theming. Anyway, he was using a perl script to generate the random selection of the theme elements, and me and my big mouth offered that it could be done in bash itself. So here we are…

Here’s my post to the CLUG mailing list the next day:


From mikal@stillhq.com Fri Mar 29 10:26:04 2002
Date: Fri, 29 Mar 2002 10:14:17 +1100 (EST)
From: Michael Still
To: Linux user group Subject: Nemo’s bash challenge for the day

Well, I said it could be done…

The brief: Generate a random number, and then return that element from a
list of elements, in bash

The code: (Assuming that the arguements on the command line are the
possible return options, and that the random number generator is running
as a separate script)

LOBOUND=0
HIBOUND=$#
shift $(( $LOBOUND + ($HIBOUND * $RANDOM) / (32767 + 1) ))
echo $1

See the attachments for some exploratory scripts I wrote while coming up
with this truncated sh. There are 54 lines of comments / white spaces, to
the 4 or so lines of actual code.

Have a nice life…

Cheers,
Mikal

PS: How good is the bash random? See the attachment output.count for a
summary of 100,000 numbers between 1 and 10 being generated with the
default seed. It’s probably good enough for most people.

PPS: If you want the code, it should also be online at
http://www.stillhq.com/cgi-bin/getpage?area=bashrand&page=index.htm in
about 30 minutes, depending when Andrew goes to sleep.

Michael Still (mikal@stillhq.com) UMT+11hrs

[ Part 2, “” Application/X-SH 2.1KB. ]
[ Unable to print this part. ]

[ Part 3, “” Application/X-SH 412bytes. ]
[ Unable to print this part. ]

[ Part 4, “” Text/PLAIN (Name: “output.count”) 2 lines. ]
[ Unable to print this part. ]

I have included some explaination of the development process I went through below for those who are interested…

Share

Getting a random number in bash

Share

This script generates a bounded random number:


#!/bin/bash

# Generate a random number. Copyright (c) Michael Still 2002
# Released under the terms of the GNU GPL
#
# (Is it possible to copyright a single line of code?)

# To quote from the rand manpage as to why we bound the random number this way:
#
# In Numerical Recipes in C: The Art of Scientific Computing
# (William H. Press, Brian P. Flannery, Saul A. Teukolsky,
# William T. Vetterling; New York: Cambridge University
# Press, 1992 (2nd ed., p. 277)), the following comments are
# made:
# “If you want to generate a random integer between 1
# and 10, you should always do it by using high-order
# bits, as in
#
# j=1+(int) (10.0*rand()/(RAND_MAX+1.0));
#
# and never by anything resembling
#
# j=1+(rand() % 10);
#
# (which uses lower-order bits).”

# To seed the random number generator, set RANDOM to a value… We can see
# that the bash code (2.05a in this case) already does some seeding for us…
#
# brand ()
# {
# rseed = rseed * 1103515245 + 12345;
# return ((unsigned int)((rseed >> 16) & 32767)); /* was % 32768 */
# }
#
# Here I have an example using the current time, which wont work well with
# multiple calls per second
#RANDOM=`date | tr -d “:” | cut -f 4 -d ” “`

# These variables just make the equation easier to read, and are not needed
LOBOUND=1
HIBOUND=10
RANDMAX=32767
BINUMBER=$(( $LOBOUND + ($HIBOUND * $RANDOM) / ($RANDMAX + 1) ))

echo $BINUMBER

Share