我在面试中使用了这个问题，我想知道最好的解决方案是什么。

编写一个Perl子程序，它接收n个列表，然后返回2 ^ n-1个列表，告诉我们哪些项目位于哪些列表中；也就是说，哪些项目仅在第一个列表，第二个列表，第一个和第二个列表以及所有其他列表组合中。假设n相当小(小于20)。

例如：

list_compare([1, 3], [2, 3]);
  => ([1], [2], [3]);

在这里，第一个结果列表给出了仅在列表1中的所有项目，第二个结果列表给出了仅在列表2中的所有项目，第三个结果列表给出了在两个列表中的所有项目。

list_compare([1, 3, 5, 7], [2, 3, 6, 7], [4, 5, 6, 7])
  => ([1], [2], [3], [4], [5], [6], [7])

在这里，第一个列表给出了仅在列表1中的所有项目，第二个列表给出了仅在列表2中的所有项目，第三个列表给出了在列表1和2中的所有项目，与第一个示例一样。第四个列表给出了仅在列表3中的所有项目，第五个列表给出了仅在列表1和3中的所有项目，第六个列表给出了仅在列表2和3中的所有项目，第七个列表给出了所有项目在所有3个列表中。

我通常将此问题作为该问题的子集(n = 2)的跟进。

解决办法是什么？

后续行动：列表中的项目为字符串。可能有重复项，但是由于它们只是字符串，因此应在输出中压缩重复项。输出列表中项目的顺序无关紧要，列表本身的顺序无关紧要。

解决方案

回答

这是我的解决方案：

构造一个哈希，其键是输入列表中所有元素的并集，并且值是位字符串，其中如果元素存在于列表i中，则设置位i。使用按位或者构造位串。然后，通过遍历哈希键，将键添加到关联的输出列表来构造输出列表。

sub list_compare {
    my (@lists) = @_;
    my %compare;
    my $bit = 1;
    foreach my $list (@lists) {
        $compare{$_} |= $bit foreach @$list;
        $bit *= 2; # shift over one bit
    }

    my @output_lists;
    foreach my $item (keys %compare) {
        push @{ $output_lists[ $compare{$item} - 1 ] }, $item;
    }

    return \@output_lists;

}

更新以包括Aristotle建议的反向输出列表生成

回答

首先，我想指出，nohat的答案根本行不通。尝试运行它，然后查看Data :: Dumper中的输出以进行验证。

就是说，问题并不恰当。看起来我们正在使用集合作为数组。我们希望如何处理重复项？我们想如何处理复杂的数据结构？我们希望元素以什么顺序排列？为简便起见，我将假定答案是壁球重复，可以对复杂的数据结构进行字符串化，并且顺序无关紧要。在这种情况下，以下是一个完全适当的答案：

sub list_compare {
  my @lists = @_;

  my @answers;
  for my $list (@lists) {
    my %in_list = map {$_=>1} @$list;
    # We have this list.
    my @more_answers = [keys %in_list];
    for my $answer (@answers) {
      push @more_answers, [grep $in_list{$_}, @$answer];
    }
    push @answers, @more_answers;
  }

  return @answers;
}

如果要调整这些假设，则需要调整代码。例如，不压扁复杂的数据结构和不压扁重复项可以使用以下方法完成：

sub list_compare {
  my @lists = @_;

  my @answers;
  for my $list (@lists) {
    my %in_list = map {$_=>1} @$list;
    # We have this list.
    my @more_answers = [@$list];
    for my $answer (@answers) {
      push @more_answers, [grep $in_list{$_}, @$answer];
    }
    push @answers, @more_answers;
  }

  return @answers;
}

但是，这是使用数据结构的字符串化来检查在一个中存在的事物是否在另一个中存在。放松这种状况将需要更多的工作。

回答

我们给定的解决方案仍然可以简化很多。

在第一个循环中，我们可以使用普通加法，因为我们只能对单个位进行"或者"运算，并且可以通过遍历索引来缩小$ bit的范围。在第二个循环中，我们可以从索引中减去1，而不是产生不需要移出的第0个输出列表元素，并且在此处不必要地重复m * n次(其中m是输出列表的数量， n是唯一元素的数量)，对唯一元素进行迭代会将迭代减少到仅n(这在m远大于n的典型用例中是一个重大胜利)，并且可以简化代码。

sub list_compare {
    my ( @list ) = @_;
    my %dest;

    for my $i ( 0 .. $#list ) {
        my $bit = 2**$i;
        $dest{$_} += $bit for @{ $list[ $i ] };
    }

    my @output_list;

    for my $val ( keys %dest ) {
        push @{ $output_list[ $dest{ $val } - 1 ] }, $val;
    }

    return \@output_list;
}

还要注意，一旦想到了这种方式，就可以借助List :: Part模块非常简洁地编写结果收集过程：

use List::Part;

sub list_compare {
    my ( @list ) = @_;
    my %dest;

    for my $i ( 0 .. $#list ) {
        my $bit = 2**$i;
        $dest{$_} += $bit for @{ $list[ $i ] };
    }

    return [ part { $dest{ $_ } - 1 } keys %dest ];
}

但是请注意，" list_compare"是一个糟糕的名字。像" part_elems_by_membership"之类的东西会更好。另外，问题Ben Tilly指出的不准确之处需要纠正。