两个列表中所有可能的对列表

Question

假设我有两个项目列表。这两个列表的长度可能相同，也可能不同。

如何生成所有可能的项目对的所有列表，其中一对由每个列表中的一个项目组成？每个项目只能是一对。

所以，如果一个列表是：

(1, 2, 3)

另一个列表是：

(a, b)

那么所有可能对的列表将是：（

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

我在 Perl 中实现这个，但显然算法是重要的一点。）

提前致谢。我的递归 foo 不起作用！

Answer 1

这是示例代码。

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);
}

示例用法：

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

请注意，如果您的列表包含 $n 和 $m 元素，则最终输出将包含 $n * ($n-1) * $m * ($m-1) / 2 元素。对于更大的列表，这会很快爆炸。阅读 http://perl.plover.com/Stream/stream.html 获取灵感如何使用这种数据结构不耗尽内存。 （或者阅读Higher Order Perl，这本书最终来自那篇文章。）