#!/usr/bin/perl
##################################################################################
# Programmer: Joshua Lande
#
# Program: all_permutations
#
# Description: This program takes as input an array of N elements. It then displays
#   every single permutation of thoes elements. For example, array ('a,'b','c') would
#   cause the output as follows:
#
#    ABC
#    ACB
#    BAC
#    BCA
#    CAB
#    CBA
#
#   The basic idea behind my solution to this program is as
#   follows. Loop through each digit in the list. Make a copy of the
#   array where the current item in the loop is switched with the
#   first item. Then, recursively call this function with the new
#   list, only looking at items in the list after the one newly
#   switched one. Whenever the function comes to a situation where
#   there are no items to switch, it should instead display the whole
#   list. When all recursive calls to this function end, all possible
#   permutation of the list have been printed out.
#
#
# The algorithm for the permeation function is as follows:
#
# Have function permute which takes in a varying sized array of items,
# and the number of items already in place.
#  
# a) If the number of items in place is greater then or equal to the
#    size of the array, display the array and return.
# b) Loop through all items in the list who's index is larger then or
#    equal to the number of items in place.
#   I) Create a copy of the array, where the current loop's item is
#      switched with the first number not in place.
#   II) Recursively call this function with an incremented number of
#       items in place and the new list
# c) End function
#
# -----
#  Jim Mahoney: I did some formatting and editing of the comments.
#
##################################################################################
use warnings;
use strict;

#my @list=('A','B','C','D','E','F','G','H','I');
my @list = 'A'..'D';   # Jim: I don't want to see 9! lines printed...
permute(@list);

##################################################################################
# Programmer: Joshua Lande
#
# function: permute
#
# Description: This function, as well as permute_help, provide the
# steps to permeate through all items in the list. It uses teh
# algorithm described in the begining of this program
#
##################################################################################
sub permute
{
  my @list=@_;
  permute_help(0,@list);
}

sub permute_help
{
  my ($index,@list)=@_;

  #print "index=$index , list=@list\n"; 
  $index=0 if ($index < 0); 
  # ensure that you are not looking outside an array

  #print "index=$index, length of list = ".(scalar @list)."\n";
  if ( $index >= scalar @list )
  {
     print " @list \n";
     return;
  }
      
  my ($new_index, @new_list);

  for (my $loop=$index;$loop<scalar @list;$loop++)
  { #loop through each item in the list which is not already in place
     @new_list=@list;
  
    #switch the desired item, so that each permuation can be tried
 
    $new_list[$index]=$list[$loop];
    $new_list[$loop]=$list[$index];
 
    #recursivly call this funtion looking at a smaller list of unplaced items

    $new_index=$index+1;
    permute_help($new_index,@new_list);    
  }
}
