I have been teaching a couple of C friends the wonders of perl for project they are working on, and they came up with a question that I found a fun answer for, and thought that it would make a great golf, so put on your plaid pants and putt about with this one...

write a subroutine that takes N arrayrefs and combines them in the following way: 

([1,2],[3,4],[5,6])
would combine as:

1 3 5
2 3 5
1 4 5
2 4 5
1 3 6
2 3 6
1 4 6
2 4 6

[download]
So, basically, all combinations that can be made using one and only one item from each array at each level.

the subroutine should return a list of array references of the combination (i.e. output for ([1],[2,3]) would be ([1,2],[1,3])) or if it is easier, a reference to an array of such references.

                - Ant
                - Some of my best work - (1 2 3)

Replies are listed 'Best First'.
Re: (GOLF) combine N arrays
by japhy (Canon) on Apr 15, 2002 at 20:23 UTC
    I wrote stuff about that here. They're called "cartesian cross-products". Someone golfed it once... I'll look for it.

    _____________________________________________________
    Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a (from-home) job
    s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

[reply]
[reply]
        Ha, mine is VERY similar to that, except I used a recursive function with nested map instead of a reversed for.. very nice...

        Ungolfed: 

        sub foo {
    my $a = shift @_;
    return [] unless $a;
    map { my $b = $_; map { [$_,@$b] } @$a } foo(@_);
}

        [download]

                        - Ant
                        - Some of my best work - (1 2 3)

[reply]
[d/l]
Re: (GOLF) combine N arrays
by jynx (Priest) on Apr 16, 2002 at 21:22 UTC

    Without looking at others solutions,

    Here's the best i can come up with. It's got a hack or two, but it seems to test out correctly. *sigh*, i am learning from the TPR challenges that i am not very good at golf, but it's still fun :)

    enjoy,
    jynx

    sub combinations {
#58+58=116
#23456789_123456789_123456789_123456789_123456789_123456789_
my@a;$;=@{$_[0]}**@_;while($a=pop){$==0;for$a((@$a)x($;>>(  
$b=@$a**@_)||1)){push@{$a[$=++]},$a for+1..$b}}@a[0..$;-1]
}

    [download]
    update: *sigh* back to the drawing board, the above version doesn't deal with multiple array lengths. The following does, but it's much longer...
    sub attempt2 {
#66+65=131
#23456789_123456789_123456789_123456789_123456789_123456789_123456789_
my%a;$-=(@_=sort{@$b<=>@$a}@_);$;=1;map$;*=@$_,@_;while($a=pop){$=
=0;for$a((@$a)x($;/@$a)){push@{$a{$=++}},$a}}grep$-==@$_,values%a
}

    [download]
[reply]
[d/l]
[select]

Back to Meditations