#!/bin/bash

# Author: Joost van Baal, 2010
# This file is in the public domain

# generate a randomly permutated sequence of integers, from 1 to the argument given

case $1 in
 [1-9]|[0-9][0-9]|[0-9][0-9][0-9]) : ;;
 *) echo first argument should be integer between 0 and 1000; exit 1 ;;
esac

# DEBUG=true
# DEBUG=false

# RANDOM Each time this parameter is referenced, a random integer between 0 and
# 32767 is generated.
maxrnd=32767
n=$1

# $DEBUG && echo maxrnd $maxrnd n $n

for i in $(seq 1 $n)
do
    rand=$(( $RANDOM * ( 1 + $n - $i ) ))
    rem=$(( $rand % $maxrnd ))

    if test $rem -gt $rand
    then
        : $(( rand += $rem ))
    else
        : $(( rand -= $rem ))
    fi

    : $(( rand /= $maxrnd ))

    while test -n "${result[$rand]}"
    do
        : $(( rand++ ))
    done

    result[$rand]=$i
done

echo ${result[@]}


# joostvb@hille:~/mariposa-permutate% strace -cF -o /tmp/s ./permutate 400
# 400 :  0.006273 seconds
# 0.009426
# 0.010814