excombine

#!/bin/sh
#-
############################################################ COPYRIGHT
#
# (c)2002-2014. Devin Teske. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
#
############################################################ INFORMATION
#
# Usage: excombine [-g] [-r range] [-c command] item1 item2 ...
#
# See `FUNCTIONS' below for a full-and-complete description of the above
# parameters.
#
# Simple Example:
#   # Print all combinations of 2 and 3 letters
#   excombine -r 2..3 a b 1 2
#   a b
#   a 1
#   a 2
#   b 1
#   b 2
#   1 2
#   a b 1
#   a b 2
#   a 1 2
#   b 1 2
#
# Advanced Example:
#   # Print all combinations where numbers add up to 13
#   excombine -c 'sum=$( echo $items | tr " " "+" ); echo $sum=$(
#       echo $sum | bc )' 1 2 3 4 5 6 7 8 | grep '=13$'
#   5+8=13
#   6+7=13
#   1+4+8=13
#   1+5+7=13
#   2+3+8=13
#   2+4+7=13
#   2+5+6=13
#   3+4+6=13
#   1+2+3+7=13
#   1+2+4+6=13
#   1+3+4+5=13
#
############################################################ GLOBALS

# Global exit status variables
SUCCESS=0
FAILURE=1

############################################################ FUNCTIONS

# f_getword $word $var_to_set $word1 $word2 ...
#
# Set variable $var_to_set to the expansion of $word against a series of
# positional arguments.
#
# Example 1:
#
#   f_getword 2 word dog bird cat # word=[bird]
#
# Example 2:
#
#   list="word1   word2   word3"
#   f_getword 3 word $list # word=[word3]
#
f_getword()
{
    local __word="$1" __var_to_set="$2"
    shift 2 # word var_to_set
    eval $__var_to_set=\"\${$__word}\"
}

# excombine [-g] [-r $range] [-c $command] $item1 $item2 ...
#
# Perform an action (`-c $command') for every combination in a list of items
# (default is to print the combination to the screen) with a given set
# (`-r num') or range of sets (`-r first..last' or `-r first-last'). See below
# for a description of each parameter.
#
# Options:
#
# -g          Don't stop if $command (default echo) returns error, but keep
#             going after an error is returned.
#
# -r $range   A number dictating how many items appear in the combinations.
#             For example: if the number `5' is used, only combinations that
#             use a total of 5 items will be calculated. If you pass the
#             number `0', all ranges will be calculated (this is the default).
#             You may also specify a range of ranges to be calculated. This can
#             be done by separating two numbers with a series of two periods or
#             a hyphen [-]. For example: passing `1..2' will (if possible)
#             calculate all combinations where both the total of items in the
#             combination are one (1) and also where the total of items in the
#             combination is two. If the range exceeds the possible total of
#             items, no error occurs; the function simply does as many sets as
#             possible. If the range is negative, it will not cause an error;
#             since this function is based on mathematics, negative values are
#             accepted but in theory and practice, have no meaning. Avoid using
#             negative values as they will have unpredictable results.
#
# -c $command The command to be executed for each iteration (e.g., `echo').
#             Note however that your command must make use of `$items' to
#             access the calculated combination for each iteration. Also note
#             that proper escaping is required to get the dollar-symbol [$] to
#             be passed in without the shell attempting to expand it (either
#             place the symbol within single-qotes or precede it with a back-
#             slash [\]).
#
excombine()
{
    local range=0 command='echo $items' keep_going=
    local startset endset

    #
    # Process optional arguments
    #
    local OPTIND flag
    while getopts "gr:c:" flag > /dev/null; do
        case "$flag" in
        g) keep_going=1 ;;
        r) range="$OPTARG" ;;
        c) command="$OPTARG" ;;
        esac
    done
    shift $(( $OPTIND - 1 ))

    #
    # Process a possible range of `sets'
    #
    case "$range" in
    *..*) startset="${range%%..*}" endset="${range##*..}";;
     *-*) startset="${range%%-*}" endset="${range##*-}";;
       *) startset="$range" endset="$range"
    esac

    #
    # Process special-case range `0' (default) to produce all range sets
    #
    local nitems=$#
    [ ${startset:-0} -eq 0 ] && startset=1
    [ ${endset:-0} -eq 0 ] && endset=$nitems

    #
    # Flip negative range values positive (pedantic)
    # NB: Negative values will throw off the math
    #
    [ $startset -lt 0 ] && startset=$(( $startset * (0-1) ))
    [ $endset -lt 0 ] && endset=$(( $endset * (0-1) ))

    #
    # Adjust values to be non-zero (mathematical constraint)
    #
    [ $startset -eq 0 ] && startset=1
    [ $endset -eq 0 ] && endset=1

    #
    # Enforce limits so we don't run over bounds
    #
    [ $startset -le $nitems ] || startset=$nitems
    [ $endset -le $nitems ] || endset=$nitems

    #
    # Set the direction of program flow (incrementing vs. decrementing)
    # NB: For the below loop through the data-set range
    #
    local next=$(( (0-1) ))
    [ $startset -le $endset ] && next=1

    #
    # Pre-register locals before entering a loop to prevent unbridled
    # memory growth (local does not check before making a variable local).
    #
    local num_subsets ncombos items combo
    local z d n # math transients
    local argnum argnums argnums_backend argnums_last argnums_new
    local setpos setpos_backend
    local seed

    #
    # Loop over each `set' in the configured direction until we hit the end
    # NB: Each `set' can represent either multiple items or a single item
    #
    local curset=$startset retval
    while [ $curset -le $endset ]; do

        #
        # Calculate number of subsets, based on the number of items in
        # the current set we're working on
        #
        num_subsets=$(( $nitems - $curset + 1 ))

        #
        # Calculate number of combinations based on number of subsets
        # NB: Using a loop here because sh(1) has no exponent operator
        # NB: sh(1), unlike bash(1), doesn't support `**' for exponent
        #
        z=1 d=1 n=0
        while [ $n -lt $curset ]; do
            z=$(( $z * ($num_subsets + $n) ))
            d=$(( $d * ($n + 1) ))
            n=$(( $n + 1 ))
        done
        ncombos=$(( $z/$d ))

        #
        # Fill $items with the initial positional arguments
        #
        # E.g., if this is a set of 2 and positional arguments are `a'
        # and `b', we'll set $items to `a b'.
        #
        n=1 items=
        while [ $n -le $curset ]; do
            eval 'items="$items ${'$n'}"'
            n=$(( $n + 1 ))
        done
        items="${items# }"

        #
        # Produce results with this first set of $items
        #
        eval $command
        retval=$?
        [ $retval -eq $SUCCESS -o "$keep_going" ] || return $FAILURE

        #
        # Prefill two `arrays' (really IFS separated strings); both
        # arrays containing a linear sequence of integers representing
        # the argv positions that we will need to reference in the
        # following subset loop.
        #
        # The first sequence ($argnums) is a linear sequence starting
        # at one (1) and ending at N (where N is the same integer as
        # the current set we're operating on). E.g., if we're currently
        # operating on a set-of-2, $argnums is set to "1 2".
        #
        # The second sequence ($argnums_backend) is a linear sequence
        # starting at $nitems-N and ending at $nitems (again, N is the
        # same integer as the current set we're operating on; $nitems
        # is the total number of items in $list). E.g., if we're
        # operating on a set-of-2, and $nitems is 8, $argnums_backend
        # is set to "7 8".
        #
        # These two arrays are used for matrix calculations below in
        # the subset loop.
        #
        n=1 argnums=
        while [ $n -le $curset ]; do
            argnums="$argnums $n"
            n=$(( $n + 1 ))
        done
        n=$curset argnums_backend=
        while [ $n -gt 0 ]; do
            argnums_backend="$argnums_backend $((
                $nitems - $n + 1
            ))"
            n=$(( $n - 1 ))
        done

        #
        # Process remaining self-similar combinations in the set
        #
        combo=1
        while [ $combo -lt $ncombos ]; do

            #
            # Using self-similarity (matrix) theorem, determine
            # (by comparing the [sliding] $argnums to the stored
            # $argnums_backend) the number of arguments that remain
            # available for shifting into a new $argnums value (for
            # later mapping into $items).
            #
            # In essence, determine when $argnums has slid into
            # $argnums_backend in which case we can mathematically
            # use the last item to find the next-new item.
            #
            n=$curset
            while [ $n -gt 0 ]; do
                f_getword $n setpos $argnums
                f_getword $n setpos_backend $argnums_backend
                #
                # If $setpos is equal to or greater than
                # $setpos_backend then we keep iterating over
                # the current set's list of argument positions
                # until otherwise; each time incrementing the
                # amount of numbers we must produce from
                # formulae rather than stored position.
                #
                argnums_last=$n
                [ $setpos -lt $setpos_backend ] && break
                n=$(( $n - 1 ))
            done

            #
            # The next few stanzas are dedicated to rebuilding
            # the $argnums pseudo-array for mapping positional
            # arguments [immediately after] into $items.
            #

            #
            # Fill an $argnums_new array (again, really just an IFS
            # separated string) with all but new/latest item(s).
            #
            n=1 argnums_new=
            while [ $n -lt $argnums_last ]; do
                f_getword $n argnum $argnums
                argnums_new="$argnums_new $argnum"
                n=$(( $n + 1 ))
            done

            #
            # Get the generator number used to populate unknown
            # positions in the matrix (using self-similarity).
            #
            f_getword $argnums_last seed $argnums

            #
            # Use the generator number to populate any position
            # numbers that weren't carried over from previous
            # combination run -- using self-similarity theorem.
            #
            n=$argnums_last
            while [ $n -le $curset ]; do
                argnums_new="$argnums_new $((
                    $seed + $n - $argnums_last + 1
                ))"
                n=$(( $n + 1 ))
            done

            #
            # Finally, assign newly calculated $argnums
            #
            argnums="$argnums_new"

            #
            # Now map the new $argnums into values stored in $items
            #
            n=1 items=
            while [ $n -le $curset ]; do
                f_getword $n argnum $argnums
                eval 'items="$items ${'$argnum'}"'
                n=$(( $n + 1 ))
            done
            items="${items# }"

            #
            # Produce results with this set of $items
            #
            eval $command
            retval=$?
            [ $retval -eq $SUCCESS -o "$keep_going" ] ||
                return $FAILURE

            combo=$(( $combo + 1 ))
        done

        curset=$(( $curset + $next ))
    done
}

# usage
#
# Print a simple usage statement and exit.
#
usage()
{
    echo "Usage: $0 [-g] [-r range] [-c command] item1 item2 ..."
    exit $FAILURE
}

############################################################ MAIN

# Print usage and exit if no arguments were passed
[ $# -gt 0 ] || usage

excombine "$@"

################################################################################
# END
################################################################################