perl - Perl でリストのすべてのサブセットを生成するにはどうすればよいですか?

Question

Perl 配列に数学セット (1, 2, 3) があります。そのセットのすべてのサブセットを見つけたいと思います: (1)、(2)、(3)、(1,2)、(1,3)、(2,3)。

要素が 3 つの場合はそれほど難しくありませんが、要素が 10 のセットの場合は難しくなります。

考え？

Answer 1

マシューが述べたようにData::PowerSetを使用できます。ただし、例に示されているように、すべてのサブセットではなく適切なサブセットのみが必要な場合は、もう少し作業を行う必要があります。

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

同様に、null セットを省略したい場合は、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);

Answer 2

Data::PowerSet、http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.htmlなどを参照してください。

Answer 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 を除外すると null セットが除外され、(1<<@$set)-1 を除外すると元のセットが除外されます。)

更新: モジュールの使用を推奨しているわけではありません。そのような問題に対処する方法を理解しようとしている場合に備えて、モジュールを使用することを提案しているだけです。一般に、各要素は、特定のサブセットに含まれるか、または除外されます。要素を選択し、最初に選択した要素を含まない他の要素の可能なサブセットをすべて生成し、次に選択した要素を含む他の要素の可能なサブセットをすべて生成します。これを「可能なすべてのサブセットを生成する」に再帰的に適用します。最後に、null サブセットと不適切なサブセットを破棄します。上記のコードでは、各要素にビットが割り当てられています。最初に上位ビットをオンにしてすべてのサブセットが生成され、次にそれをオフにしてすべてのサブセットが生成されます。これらの選択肢のそれぞれについて、サブセットが最初に生成され、次の最上位ビットがオフになり、次にオンになります。

Answer 4

これはカウントの問題です。N個の要素には正確に2^N個のサブセットがあり、それらすべてを一覧表示するには、バイナリで0から2^N-1までカウントする必要があります。

たとえば、3つのアイテムの場合、8つの可能なサブセットがあります：000、001、010、011、100、101、110、および111-数字はどのメンバーが存在するかを示します。

Answer 5

Algorithm::ChooseSubsetsを使用します。