:
##########################################################################
# Title      :	permute - print permutations
# Author     :	Heiner Steven <heiner.steven@odn.de>
# Date       :	2005-01-19
# Category   :	Text Utilities
# Requires   :	nawk
# SCCS-Id.   :	@(#) permute	1.2 05/01/19
##########################################################################
# Description
#	Prints all permutations of the input arguments, e.g.
#	    $ permute a b c
#	results in
#	    a b c
#	    a c b
#	    c a b
#	    c b a
#	    a b c
#	    a c b
#
#	Since the number of output lines is the factorial of the number
#	of arguments, the resulting output can be very large. Three
#	arguments produce 3*2*1 = 6 lines of output, 5 arguments result
#	in 5*4*3*2*1 = 120 lines, 10 arguments already yield 3628800
#	output lines. Use with care.
#
# Notes
#    o	Elements cannot have embedded whitespace (this could be changed
#	in the AWK program by defining a distinct delimiter)
#    o	All elements must fit into one single AWK string
##########################################################################

PN=`basename "$0"`			# Program name
VER='1.2'

# Uncomment the following line to disable the auto-detection below:
#: ${NAWK:=nawk}

usage () {
    echo >&2 "$PN - print permutations, $VER
usage: $PN [-h] arg [arg ...]
   -h:  print this usage summary

Prints all permutations of the arguments.

Note that the number of output lines is the factorial of the number of
the command line arguments, which increases fast:

	# of arguments	# of output lines
	-------------- 	-----------------
	2		2
	3		3*2*1 = 6
	...
	10		3628800"
    exit 1
}

msg () { echo >&2 "$PN:" "$@";  }

fatal () { msg "$@"; exit 1; }

###############################################################################
# searchprog - search program using search PATH
# usage: searchprog program
###############################################################################

searchprog () {
    _search=$1; shift

    for _dir in `echo "$PATH" | sed "s/^:/.:/;s/:\$/:./;s/:/ /g"`
    do
        [ -x "$_dir/$_search" ] || continue
        echo "$_dir/$_search"
        return 0
    done

    return 1
}

# We need a "new" NAWK implementation with functions
: ${NAWK:=`searchprog mawk || searchprog gawk || searchprog nawk || echo awk`}

while [ $# -gt 0 ]
do
    case "$1" in
        --)     shift; break;;
        -h)     usage;;
        -*)     usage;;
	*)	break;;
    esac
    shift
done

[ $# -lt 1 ] && usage

echo "$*" |
    $NAWK '
    	# permute - print permutations of elem[start...n]

	function permute(s, start, 		i, j, n, tmp) {

	    # We need a copy of all elements (elem[]) for each instance
	    # of this recursively called function. Since AWK does never
	    # keep a copy of an array, we use the string "s" as storage.

	    n = split(s, elem)
	    if (start > n) {			# End of recursion
	    	print s
		return
	    }

	    # Put each element in turn to the front of the list, and
	    # print all permutations starting with this element.

	    for (i=start; i<=n; i++) {
	    	if (i != start) {
		    # Exchange elem[start] and elem[i]
		    tmp = elem[start]; elem[start] = elem[i]; elem[i] = tmp
		    nextstr = elem[1]
		    for (j=2; j<=n; j++) nextstr = nextstr delim elem[j]
		} else {
		    nextstr = s
		}

		# Recursively process all possible lists, keeping only
		# the first elementof the list constant.

		permute(nextstr, start+1)

		# The previous recursion probably modified our global
		# elem[] array. We have to reset it using our initial
		# input parameter "s"

		n = split(s, elem)
	    }
	}

	BEGIN {
	    delim = " "			# output field separator
	}

        {
	    # Recursively print all permutations of all fields in the
	    # input line
	    permute($0, 1)
	}
    '