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

#
# anagrams, permutations, etc
#
# 25 Feb 2000
#

package Anagrams;

######################################################################

BEGIN {
	 my @factorials = (1);

	 sub factorial {
		  my $n = shift;
		  if (defined @factorials->[$n]) {
				## nothing
		  }
		  else {
				@factorials->[$n] = $n * &factorial($n-1);
		  }
		  return @factorials->[$n];
	 }
}
######################################################################
#
# Usage: &integer2pattern( $n, $len ) produces $n-th pattern of length $len
#

sub integer2pattern {
	 my $n = shift;
	 my $len = shift;
	 my $i = 1;
	 my @pattern = ();
	 while ($i <= $len) {
		  push @pattern, $n % $i; ## sure, first pushes 0
		  $n = int( $n/$i );
		  $i++;
	 }
	 return \@pattern;
}

######################################################################
#
# Usage: pattern2permutation( \@pattern, @set ) 
# 
# Consumes @pat
# @set passed NOT by ref therefore gets _copied_
#

sub pattern2permutation {
	 my $pat = shift;
	 my @set = @_;
	 my @permed = ();
	 while (@$pat){
		  push @permed, splice( @set, (pop @$pat), 1);
	 }
	 return @permed;
}

######################################################################
#
# Usage integer2permutation( $which_perm , @set )
# 

sub integer2permutation {
	 my $n = shift;
	 my @set = @_;
	 return &pattern2permutation( &integer2pattern($n, scalar(@set)), 
								  @set);
}
######################################################################
#
# Usage permuteString( $which, $string )
#

sub permuteString {
	 my $n = shift;
	 my $str = shift;
	 return integer2permutation( $n, split(//, $str ) );
}

######################################################################
#
# the oft-forgotten:
#

1;

######################################################################