5

我在 Perl 数组中有一个数学集：(1, 2, 3)。我想找到该集合的所有子集：(1)、(2)、(3)、(1,2)、(1,3)、(2,3)。

使用 3 个元素这并不太难，但如果 set 有 10 个元素，这会变得很棘手。

想法？

4

6 回答 6

12

您可以像 Matthew 提到的那样使用Data::PowerSet 。但是，如果如您的示例中所示，您只需要适当的子集而不是每个子集，则需要做更多的工作。

  # result: all subsets, except {68, 22, 43}.
  my $values = Data::PowerSet->new({max => 2}, 68, 22, 43);

同样，如果要省略空集，只需添加min参数：

  # result: all subsets, except {} and {68, 22, 43}.
  my $values = Data::PowerSet->new({min => 1, max => 2}, 68, 22, 43);

否则，要获取所有子集，只需省略两个参数：

  # result: every subset.
  my $values = Data::PowerSet->new(68, 22, 43);
于 2009-06-15T01:50:27.200 回答
4

请参阅Data::PowerSet、http ://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html等。

于 2009-06-15T01:43:44.080 回答
3

既然您说“数学集”，我假设您的意思是没有重复项。

适用于多达 32 个元素的简单实现：

my $set = [1,2,3];
my @subsets;
for my $count ( 1..(1<<@$set)-2 ) {
    push @subsets, [ map $count & (1<<$_) ? $set->[$_] : (), 0..$#$set ];
}

（对于全范围的子集，从 0 循环到 (1<<@$set)-1；排除 0 排除空集，排除 (1<<@$set)-1 排除原始集。）

更新：我不提倡使用模块，只是建议它以防你想了解如何解决这样的问题。一般来说，每个元素要么被包含在任何给定的子集中，要么被排除在外。您想选择一个元素并首先生成其他元素的所有可能子集，不包括您选择的元素，然后生成其他元素的所有可能子集，包括您选择的元素。递归地将其应用于“生成所有可能的子集”。最后，丢弃空子集和非正确子集。在上面的代码中，每个元素都被分配了一个位。首先，所有子集都是在高位打开的情况下生成的，然后是所有子集都关闭的。对于这些备选方案中的每一个，首先生成子集，将次高位关闭，然后再打开。

于 2009-06-15T02:04:35.713 回答
1

使用算法::ChooseSubsets。

于 2009-06-15T01:52:45.383 回答
1

如果您不想使用现有模块或不能，那么您可以简单地使用位掩码和二进制计数器编写您自己的子集生成算法。示例代码如下 -

#!/usr/bin/perl
use strict;
use warnings;

my @set     = (1, 2, 3);
my @bitMask = (0, 0, 0); #Same size as @set, initially filled with zeroes

printSubset(\@bitMask, \@set) while ( genMask(\@bitMask, \@set) );

sub printSubset {
  my ($bitMask, $set) = @_;

  for (0 .. @$bitMask-1) {
    print "$set->[$_]" if $bitMask->[$_] == 1;
  }
  print"\n";

}

sub genMask {
  my ($bitMask, $set) = @_;

  my $i;
  for ($i = 0; $i < @$set && $bitMask->[$i]; $i++) {
    $bitMask->[$i] = 0;
  }

  if ($i < @$set) {
    $bitMask->[$i] = 1;
    return 1;
  }

  return 0;
}

注意：我无法测试代码，可能需要解决一些错误。

于 2009-06-15T02:25:25.447 回答
1

这是一个计数问题 - 对于 N 个元素，恰好有 2^N 个子集，您必须从 0 到 2^N - 1 以二进制数计数才能将它们全部列出。

例如，3 个项目有 8 个可能的子集：000、001、010、011、100、101、110 和 111 - 数字显示存在哪些成员。

于 2009-11-21T08:07:42.227 回答