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

发布于 2024-11-02 00:38:27 字数 364 浏览 0 评论 0原文

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

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

所以，如果一个列表是：

(1, 2, 3)

另一个列表是：

(a, b)

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

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

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

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

原文

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!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

空气里的味道 2024-11-09 00:38:27

这是示例代码。

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，这本书最终来自那篇文章。）

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.)

回复收藏 0 原文

~没有更多了~