CODEWITHSUNDEEP
algorithmrecursioncombinations
user714138
user714138

Reputation:

All possible lists of pairs from two lists

Suppose I have two lists of items. The two lists may or may not be the same length.

How can I generate all the lists of all possible pairs of items, where a pair consists of an item from each list? Each item can only be in a single pair.

So, if one list is:

(1, 2, 3)

And the other list is:

(a, b)

Then the lists of all possible pairs would be:

(1a, 2b)
(1a, 3b)
(1b, 2a)
(1b, 3a)
(2a, 3b)
(2b, 3a)

(I'm implementing this in Perl, but obviously the algorithm is the important bit.)

Thanks in advance. My recursion foo isn't working!

Upvotes: 0

Views: 434

Answers (1)

btilly
btilly

Reputation: 46409

Here is sample code.

use strict;
use warnings;

sub unordered_pairs {
    return if @_ < 2;
    my $first = shift;
    return (map [$first, $_], @_), unordered_pairs(@_);
}

sub cartesian_product {
    my @answers = [];
    for my $list (@_) {
        @answers = map {
            my $value = $_;
            map [@$_, $value], @answers
        } @$list;
    }
    return @answers;
}

sub possible_pairs_of_pairs {
    my ($list1, $list2) = @_;

    my @pairs1 = unordered_pairs(@$list1);
    my @pairs2 = unordered_pairs(@$list2);

    return map {
        [[$_->[0][0], $_->[1][0]], [$_->[0][1], $_->[1][1]]],
        [[$_->[0][0], $_->[1][1]], [$_->[0][1], $_->[1][0]]],
    } cartesian_product(\@pairs1, \@pairs2);
}

And sample usage:

use Data::Dumper;
my @stuff = possible_pairs_of_pairs([1, 2, 3], ['a', 'b']);
print Dumper(\@stuff);

Be warned that if your lists have $n and $m elements, the final output will have $n * ($n-1) * $m * ($m-1) / 2 elements. This will blow up very quickly with larger lists. Read http://perl.plover.com/Stream/stream.html for inspiration on how to not run out of memory with that kind of data structure. (Or read Higher Order Perl, the book that eventually came out of that article.)

Upvotes: 0

Related Questions