0

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

编写一个 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 的此问题子集的后续问题。

解决办法是什么？

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

4

3 回答 3

2

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

在第一个循环中，您可以使用简单的加法，因为您只使用单个位进行 ORing，并且您可以$bit通过迭代索引来缩小范围。在第二个循环中，您可以从索引中减去 1，而不是生成需要删除的不必要的第 0 个输出列表元素shift，并且您不必要地迭代 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 指出的问题中的不精确之处需要纠正。

于 2008-09-16T09:33:47.660 回答
1

首先，我想指出 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;
}

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

于 2008-09-16T07:18:43.477 回答
0

这是我的解决方案：

构造一个哈希，其键是输入列表中所有元素的并集，值是位字符串，如果元素存在于列表 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;

}

更新以包括亚里士多德建议的反向输出列表生成

于 2008-09-16T01:05:47.430 回答