use strict;
use warnings;

my $n = 0;
my $total = 0;
my $num_left = 0;
my @order;

sub factorial {
    my $input = CORE::int(shift);
    return "Error - unable to take factorial of an negative number ($input)" if $input < 0;
    return "Error - factorial result is greater than system limit ($input)" if $input > 170;
    return 1 if $input == 0;
    my $result = 1; 
    for (my $i=2; $i<=$input; $i++) { $result *= $i }
    return $result;
}

sub init {
    my ($size) = @_;
    @order = (0..$size-1);
    $n = $size;
    $total = $num_left = &factorial($size);
}

sub get_next {
    if ($num_left == $total) {
	$num_left--;
	return @order;
    }


    # Find largest index j with a[j] < a[j+1]

    my $j = scalar(@order) - 2;
    while ($order[$j] > $order[$j+1]) {
	$j--;
    }

    # Find index k such that a[k] is smallest integer
    # greater than a[j] to the right of a[j]

    my $k = scalar(@order) - 1;
    while ($order[$j] > $order[$k]) {
	$k--;
    }

    # Interchange a[j] and a[k]

    @order[($k,$j)] = @order[($j,$k)];

    # Put tail end of permutation after jth position in increasing order

    my $r = scalar(@order) - 1;
    my $s = $j + 1;

    while ($r > $s) {
	@order[($s,$r)]=@order[($r,$s)];
	$r--;
	$s++;
    }

    $num_left--;
    return(@order);
}

&init(9);
while($num_left) {
    print(join(':',&get_next()).$/);
}