[Wellington-pm] Combinatorics

[Simon Green]

On 04/07/17 21:45, Peter Kelly wrote:
> So, let me start with a confession - I stopped at sixth form maths.  
> 
> The programme I am trying to write this evening seeks to combine one
> element of set A, with one element of set B, one element of set C, etc.
> 
> I don't know beforehand how many sets there will be.   Each set has a
> different number of members.
> 
> I need to test all the combinations, so that if we have sets A B C, and
> A has 2 items, B has 5 items, and C has 2 items, we end up with 2*5*2
> combinations = 20.
> 
> k possible combinations of items in a single set is conveniently
> available through Algorithm::Combinatorics.  I've used that elsewhere in
> this programme but it doesn't seem to handle multiple sets.
> 
> I've spent the last few hours on this, and have started a few ways.  I
> have something written using recursion, tracking which sets have already
> been accessed using an arrayref, and passing around a hashref.  But I am
> seriously bogged down in that "delete the code and start again" sort of way.
> 
> Are there any better ideas that any of you can point me to?

Something like the below. I'm sure there is a more eloquent way to write
it, but it does the job and sometimes that's good enough™

-- 
Simon

#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;
use 5.10.1;

my @sets = ( [2,3,4], [3,4,5], [6,7,8], [10,12,13]);
my @results = ();


sub _combinate {
    my ($result, $group, $set, @sets) = @_;
    foreach my $item (@$set) {
        if (scalar(@sets)) {
        _combinate($result, [@$group, $item], @sets);
        }
        else {
            push @$result, [ @$group, $item ];
        }
    }
}

_combinate(\@results, [], @sets);
say Dumper(\@results);