#!/usr/bin/perl
# Canadian Computing Competition
#
# Example program to demonstrate input and output and time limit.
#
# Programming Language: Perl
#
# Specification:
#
# Write a program that reads several positive integers, one per
# line. For each integer n, output the number of orderings
# possible for a set of n distinct values. n will not exceed 11.
# The last line of input is indicated by 0.
#
# Sample Input:
#
# 1
# 9
# 0
#
# Output for Sample Input:
#
# 1
# 362880
#
# Implementation:
#
# The answer is n! (n factorial) which is easily computed in n steps.
# But this program does it the hard way. It uses a recursive function
# to enumerate and count all the possible orderings.
#
# How to run the program:
#
# The program reads from "standard input" and writes to "standard output."
# That is, you can run this from the command line by typing:
# perl test.pl < in1
# where in1 is a file which contains the input numbers, one per line.
# Standard output can also be redirected to a file. If it is not
# redirected, it will show up on the terminal.
#
# Run-time:
#
# Please time the execution time of this program on your computer,
# using the sample input. This time is the maximum that should be
# allowed for any CCC program. Note that problems up to size 9 can
# be solved using the algorithm below, though there are more efficient
# solutions (such as just multiplying n times) which would run in
# time
sub countfact {
my $k = shift;
my $n = shift;
my $sref = shift;
my @s = @{$sref};
local $r=0;
local $i, $t;
if ($k eq 0) {
# uncomment to print out each ordering
# for($j=0; $j<$n; $j++) printf("%d ", $s[$j]);
# printf("\n");
return 1;
}
for ($i=0; $i<$k; $i++) {
$t = $s[$i];
$s[$i] = $s[$k-1]; # Swap two positions
$s[$k-1] = $t;
$r += &countfact($k-1,$n,\@s); # Count
$s[$k-1] = $s[$i]; # Unswap
$s[$i] = $t;
}
return $r;
}
@s = (1..11);
$n = 1;
while ($n != 0) {
$n = ;
printf("%d\n",&countfact($n,$n,\@s));
}