#!/usr/local/bin/perl -w

package Math::Combinatorics::Combinator;

####################################################################
#
# Math::Combinatorics::Combinator
# Version 0.90    22 April 2001
# Copyright 2001, Alexander Scouras
# All Rights Reserved
# Bug reports or comments may be sent to lexicon@anapraxis.net
#
# This program is free software.
# It may be distributed and/or modified under either the
# Perl Artistic License or the GNU General Public License.
#
####################################################################
#
# This is a combinatorics module for Perl.  I assume anyone digging
# around in here knows their Combinatorics.  This is going to be a
# quick couple of paragraphs describing how this code 'thinks about'
# a combination in terms of it's data structure.  One might breeze
# through the POD before reading this for a refresher.
#
# Each $Element in the @Combination has a certain range.  The size
# of this range is $Holes, as described in the POD.  Everything
# describing an $Element's Index is a reference to which of its own
# $Holes it occupies in the @Combination.  @Combination is usually
# stored as a collection of $Holes indexes.  At the end of
# &Combinate, the actual @Combination is created by adding an
# $Element's $Index to the rank of the $Element itself (0th through
# R-1'th elements), and using this as an index into the @Master to
# find the value. The input (to Decombinate) and output (from
# Combinate) of actual elements is in the @Combination array.
#
# So how does it determine which $Elem ends up in which of its
# $Holes?  The cool stuff is in RANDOM &Combinate and &Decombinate.
# In RANDOM, all the majic happens in the @Steps_Incr / @Steps_Zero
# population.  There we determine how many @Steps it takes to place
# an $Elem into a given $Index.  Basically, we brute force calculate
# it by running through all the posibilities of Lexicographic
# Ordering.  @Steps_Incr takes this a step at a time, then
# @Steps_Zero gives us some shortcuts for later calculations.  All
# this happens during Initialize.
#
# Next we will discuss the actual RANDOM &Combinate process only.
# For &Decombinate, you do all this in reverse (with a couple
# extra steps discussed there).  Starting with the lower #Elem's,
# we try to allocate off $Steps from our $Combindex.  For each
# $Elem, we test (using @Steps_Zero) how high it's index can reach,
# pushing it as high as $Combindex will let us.  Finding the max, we
# allocate that many $Steps to that $Elem and move to the next.  We
# then add the previous $Elem's $Index to the current one to
# maintain order and avoid repeating previous @Combinatinos.
# Repeat the process till we get to the second to last $Elem.  If
# there are any unallocated $Steps, we add them to the last $Elem,
# as well as the 2nd to last's $Index, of course.
#
# The LINEAR algorithm is discussed where it is implimented, and is
# easy to understand simply by examining the code (once one
# understands this $Holes concept anyway).
#
####################################################################

# Constants for the Object Properties Array

my $C = 0; # Constant Count
use constant MASTER         => $C++;  # Source Array
use constant N              => $C++;  # Size of Source Array
use constant R              => $C++;  # Size of Sub-Set
use constant HOLES          => $C++;  # Possible values for an Elem
use constant COMBINDEX      => $C++;  # Index of the Combination
use constant ABSTRACT       => $C++;  # Array with Sub-Set,
use constant MIN_COMBINDEX  => $C++;  # Minimum Index, always 0
use constant MAX_COMBINDEX  => $C++;  # Maximum Index.Choose(N,R)
use constant STEPS_INCR     => $C++;  # Steps to Index from 0
use constant STEPS_ZERO     => $C++;  # Steps to Index from previous

use strict;
use Math::Combinatorics qw(:common);

$Math::Combinatorics::Combinator::VERSION
            = 0.90;   # v1.00 Release Candidate.



####################################################################
#   INITIALIZE COMBINATOR (
#                $Return_Size # Size of the set to return
#                @Master,     # The array that will be operated on
#              )
####################################################################
# Constructor which Initializes a $Combinator for producing
# R-Combinations from a given @Master.
####################################################################

sub Initialize {
  my $s               = [];
  bless $s;

  $s->[R            ] = shift;
  $s->[MASTER       ] = shift;
  $s->[N            ] = scalar @{$s->[MASTER]};
  $s->[HOLES        ] = $s->[N] - $s->[R] + 1;
  $s->[COMBINDEX    ] = -2;
  $s->[ABSTRACT     ] = [];
  $s->[MIN_COMBINDEX] = 0;
  $s->[MAX_COMBINDEX] = Choose($s->[N], $s->[R]) - 1;

  $s->Init_Steps_Incr();
  $s->Init_Steps_Zero();

  return $s;

}

####################################################################
#   @STEPS (INCREMENTALY) [ ELEMENT ] [ INDEX ]
####################################################################
# This is a 2 dimensional array of the steps between INDEX-1 and
# INDEX at the same HEIGHT.
####################################################################

sub Init_Steps_Incr {
  my $s           = shift;
  my $R           = $s->[R];
  my $Holes       = $s->[HOLES];
  my @Steps_Incr;

  for (my $e = $R-1; $e >= 0; $e--) {
    $Steps_Incr[$e] = [];         # Create subarray
    # 0th Index: Default location, takes no steps;
    $Steps_Incr[$e][0] = 0;
    for my $i (1..$Holes-1) {
      # Last Element: moves one step at a time
      if    ($e == $R-1) { $Steps_Incr[$e][$i] = 1 }
      # First Index: the Sum of the Steps of Prev Element + 1;
      elsif ($i == 1) {
        $Steps_Incr[$e][$i] = 1;
        for my $x ($i..$Holes-1) {
          $Steps_Incr[$e][$i] += $Steps_Incr[$e+1][$x] }}
      # Normally: Steps to Prev Index
      #         - Steps to Prev Height's Prev Index
      else {
        $Steps_Incr[$e][$i] =
          $Steps_Incr[$e  ][$i-1] -
          $Steps_Incr[$e+1][$i-1]}
    }
  }

  $s->[STEPS_INCR] = \@Steps_Incr;

}

####################################################################
#   @STEPS (FROM ZERO) [ HEIGHT ] [ INDEX ]
####################################################################
# This is an array of the number of steps necessary to place an
# element at HEIGHT in Return_Size to a given INDEX in the Holes.
#
# This relies on @Steps_Incr for it's base calculations.
####################################################################

sub Init_Steps_Zero {
  my $s           = shift;
  my $R           = $s->[R];
  my $Holes       = $s->[HOLES];
  my @Steps_Zero;
  my @Steps_Incr  = @{$s->[STEPS_INCR]};

  for (my $e = $R-1; $e >= 0; $e--) {
    $Steps_Zero[$e] = [];
    # 0th Index: Default location, takes no steps;
    $Steps_Zero[$e][0] = 0;
    # 1st Index: Same as Steps_Incr ( same base for calculation (0))
    $Steps_Zero[$e][1] = $Steps_Incr[$e][1];
    # Normally: Steps to Prev Index + Steps to Next Index
    for my $i (2..$Holes-1) {
      $Steps_Zero[$e][$i] =
        $Steps_Incr[$e][$i] +
        $Steps_Zero[$e][$i-1];
    }
  }

  $s->[STEPS_ZERO] = \@Steps_Zero;

}




####################################################################
#   COMBINATE (
#                 $COMBINATION,   # WHICH COMBINATION OF ARRAY
#              )
####################################################################
# Returns the COMBINATION th R-Combination of an ARRAY as enumerated
# in Lexicographic Order.  R and ARRAY are received by COMBINATOR
# during the INIT_COMBINATOR initialization.
####################################################################

sub Combinate {

  my $s           = shift;
  my $R           = $s->[R];
  my $N           = $s->[N];
  my $Holes       = $s->[HOLES];
  my @Master      = @{$s->[MASTER]};
  my @Abstract    = @{$s->[ABSTRACT]};

  my $Combindex   = shift;

  die "The combination $Combindex is out of range.  " .
      "Valid indexes are between $s->[MIN_COMBINDEX] and " .
      "$s->[MAX_COMBINDEX] for an array of size $s->[N]"
      if ($Combindex < $s->[MIN_COMBINDEX]
      ||  $Combindex > $s->[MAX_COMBINDEX]);

  #------------------ LINEAR ALGORITHM -----------------------------
  # We save the @Combination from previous calculations and simply
  # increment it to the next @Combination.  This basically means
  # incrementing later elements to their max, then incrementing the
  # next element and resetting its followers to its value and doing
  # it all over again.
  #-----------------------------------------------------------------

  if ($s->[COMBINDEX] + 1 == $Combindex) {
    $s->[COMBINDEX] = $Combindex;
    my $Elem = $R - 1;
    while ($Abstract[$Elem] == $Holes-1) { $Elem-- }
    my $New_Index = ++$Abstract[$Elem];
    for my $Elem2 ( $Elem+1..$R-1 ) {
      $Abstract[$Elem2] = $New_Index;
    }

  #------------------ RANDOM ALGORITHM -----------------------------
  # RANDOM goes through the elements in order and gives them as high
  # an index as possible based on the current combination.  When an
  # earlier element is pushed as far as possible, the next element
  # is started from wherever the earlier element stopped.  This 
  # keeps the elements in order.
  #
  # Calculating the steps properly involved some special math in the
  # two steps arrays and a timely subtraction of the extra index
  # gained from earlier incremented elements.
  #
  # The first thing to occur is to save the $Combindex, as it will
  # be destroyed later when calculating later elements.
  #-----------------------------------------------------------------
  } else {

    my $R               = $s->[R];
    my $N               = $s->[N];
    my $Holes           = $s->[HOLES];
    my @Steps_Zero      = @{$s->[STEPS_ZERO]};
    my $Steps           = 0;
       $s->[COMBINDEX]  = $Combindex;
       $Abstract[0]     = 0;

    ELEM:  #For all but the last element:
    for my $Elem (0..$R-2) {
      # The index of earlier elements is added to later ones
      $Abstract[$Elem] = $Abstract[$Elem-1] if $Elem > 0;
      # Temp storage of the Element's index.
      my $Index = $Abstract[$Elem];
      # Partial Steps, a subcount of steps for the element
      my $pSteps = 0;

      # An infinite loop but:
      while (1) {
        # We can break when the index reaches the maximum ($Holes)
        # Set the combination to the maximum and exit all loops.
        if ($Index == $Holes-1)   { $Combindex       = 0;
                                    $Abstract[$Elem] = $Index;
                                    next ELEM
                                  }
        # Check how many steps to increment the index one more time
        $Steps = $Steps_Zero[$Elem][$Index+1]
               - $Steps_Zero[$Elem][$Abstract[$Elem]];
        # If we have that many steps left, Increment the Index and
        # note (in $pSteps) how many steps it takes to reach it
        if ($Combindex >= $Steps) { $Index++;  $pSteps = $Steps }

        # If we do not have that many steps left, subtract the
        # pSteps from the Combindex, set the element, and move to
        # the next element to pass some indicies into.
        else                      { $Combindex      -= $pSteps;
                                    $Abstract[$Elem] = $Index;
                                    next ELEM
                                  }
      }
    }
    # Any left over steps are given to the last element.


    $Abstract[$R-1]  = $Combindex;
    $Abstract[$R-1] += $Abstract[$R-2] unless $R < 2;
  }

  #------------------ PRODUCE SUBSET FROM INDICES ------------------
  # Here the actual @Combination is produced, in the array
  # @New_Combination.  We leave @Combination untouched for use in
  # future calls to the LINEAR algorithm.
  #
  # The $Elem's $Index is added to it's own rank (0th element += 0,
  # 4th element += 4, etc...) and this number is used as an index
  # into the @Master.  The appropriate element from the @Master is
  # copied into it's place in the @New_Combination, for all elements
  # and the @New_Combination is returned as the actual SubSet.
  #-----------------------------------------------------------------


  $s->[ABSTRACT] = \@Abstract;

  my @Combination = ();
  for my $Elem (0..$R-1) {
    $Combination[$Elem] = $Master[$Abstract[$Elem] + $Elem]
  }
  return @Combination;
}


####################################################################
#   DECOMBINATE (
#                 @COMBINATION  # WHICH COMBINATION OF THE ARRAY
#               )
####################################################################
# Processes a set and determines it's Lexicographic Index as an
#   R-Combination of an Array determined in &Init_Combinator;
####################################################################

sub Decombinate {

  my $s           = shift;

  my @Combination = @{+shift};
  my $R           = $s->[R];
  my $N           = $s->[N];

#  my @Abstract   = @{$s->[ABSTRACT]};
  my @Steps_Zero = @{$s->[STEPS_ZERO]};
  my @Master     = @{$s->[MASTER]};

  die '@Combinations passed to Decombinate must be the same size ' .
      'as R from initialization.  R=' .
       $R . ' and $@Combination=' . scalar(@Combination)
      if (scalar (@Combination) != $R);

  my $Combindex;        # Lexicographical Index of the R-Combination
  my $Elem = 0;         # Element of the Return Set
  my $Index;            # Index of an individual $Elem
  my @Master_Abstract;  # Index representation of @Master
  my @Abstract;         # Index representation of @Combination
     $Abstract[$_] = 0 for (1..$R);

  # Abstract @Combination to its array indicies (causes sort)
  #  If the element is in the @Combination, the corresponding bit
  #  in the @Master_Abstract is turned on.

  for (my $i = 0; $i < $R; $i++) {
    for (my $j = 0; $j < $N;  $j++) {
      if ($Combination[$i] eq $Master[$j]) {
        $Master_Abstract[$j] = 1 ;
      }
    }
  }

  # Now, going through the $Master_Abstract in order, calculate the
  #  $Combindex.  This is, the steps to push this @Combination
  #  element to the correct element in the @Master, minus the steps
  #  it had already gained from previous elements pushing it up.

  for (my $i = 0; $i < scalar(@Master_Abstract); $i++) {
    next unless $Master_Abstract[$i];
    $Index = $Abstract[$Elem] = $i - $Elem;
    $Combindex += $Steps_Zero[$Elem][$Index]
                - $Steps_Zero[$Elem][$Abstract[$Elem-1]];
    $Elem++;
  }
  return $Combindex;
}

1;

# The POD, almost as long as the code itself, 
# has been left off.  You may find it at:
# http://code.anapraxis.net
[download]