#!/usr/bin/perl -w
# grouped_permutation.pl: generating grouped permutations
# KUBO Takuya, 2002.04.12
use strict;
use Algorithm::Permute;

my ($group_size, $max) = (3, 9); # Setting #

die "ERROR: Invalid set (\$max, \$group_size) = ($max, $group_size)"
	if $max % $group_size != 0;
my $group_number = $max / $group_size;
my $all_permutations = new Algorithm::Permute([1 .. $max]);

sub compare_within_group {
	my ($list, $group_size) = @_;
	my ($i, $return_val) = (1, 1);
	my $previous = shift @$list;
	while (@$list > 0 and $return_val == 1 and $i++ < $group_size) {
		my $here = shift @$list;
		$return_val = 0 if $here < $previous;
		$previous = $here;
	}
	return $return_val; # 1: true, 0: false
}

LOOP: while (my @permutation = $all_permutations->next) {
	my @copy = @permutation;
	my $first_check = 1;
	while (@copy > 0 and $first_check == 1) {
		$first_check = compare_within_group(\@copy, $group_size);
	}
	next LOOP if $first_check == 0;
	my @group_head;
	foreach my $i (0 .. ($group_number - 1)) {
		push @group_head, $permutation[$i * $group_size];
	}
	print join(" ", @permutation)."\n"
		if compare_within_group(\@group_head, $group_number) == 1;
}

