package main;

use strict;
use warnings;


my @gPeople = sort ('Sue', 'Jim', 'Pat', 'Don', 'Bob', 'Joe', 'Liz', 'Ned');
use constant kMaxGroupSize => 6;


my $solution_count = 0;
my %seen_solution = ();

sub permute_people
{
	my ($groups_ref, $items_list_ref, $perms_list_ref) = @_;
	
	my @groups = @{ $groups_ref };
	my @items = @{ $items_list_ref };
	my @perms = @{ $perms_list_ref };
	
	if (scalar(@items) == 0) 
	{
		my (@newperms) = ();	
		
		foreach my $group (@groups)
		{
			my @group_items = sort splice(@perms, 0, $group);
			
			return if (grep($_ eq 'Bob', @group_items) && grep($_ eq 'Joe', @group_items));
			return if (grep($_ eq 'Liz', @group_items) && grep($_ eq 'Ned', @group_items));
			
			push (@newperms, "(@group_items)");
		}
		@newperms = sort @newperms;
		
		if (!$seen_solution{"@newperms"}++)
		{
			$solution_count++;
			print "  @newperms\n";
		}			
	}
	else 
	{
		my (@newitems, @newperms, $selected);
		
		foreach my $i (0 .. $#items)
		{
			@newitems = @items;
			@newperms = @perms;
			
			$selected = splice(@newitems, $i, 1);
			push(@newperms, $selected);
			permute_people($groups_ref, [@newitems], [@newperms]);
		}
	}
}


my %seen_group = ();

sub permute_group_size
{
	my ($perms_list_ref, $max_group_size, $people) = @_;

	my @perms = @{ $perms_list_ref };
	
	if ($people == 0) 
	{
		@perms = sort {$b <=> $a} @perms;
		if (!$seen_group{"@perms"}++)
		{
			print "\nGroup size template: @perms\n";
			permute_people(\@perms, \@gPeople, []);
		}
	}
	elsif ($people > 0) 
	{
		foreach my $i (1 .. $max_group_size)
		{
			my @newperms = @perms;
			push(@newperms, $i);
			permute_group_size([@newperms], $max_group_size, $people - $i);
		}
	}
}


permute_group_size([], kMaxGroupSize, scalar(@gPeople));

print "\nSolutions: $solution_count\n";