perl - 如何在 Perl 中创建所有大小小于 n 的子集？

Question

我有一套。我想创建所有集合，这些集合最多从每个原始集合中获取一个元素。例如，如果我的原始集合是 ((x,y),(A),(1,2)) 那么解决方案是:

(x)
(y)
(A)
(1)
(2)
(x,A)
(x,1)
(x,2)
(y,A)
(y,A)
(y,1)
(y,2)
(A,1)
(A,2)
(x,A,1)
(x,A,2)
(y,A,1)
(y,A,2)

我使用我编写的以下代码递归计算:

# gets an array of arrays (aoa)
# returns an array of arrays with all subsets where zero or one element is
# taken from each array, e.g. in = [[a,b],[5],[X,Y,Z]], out =
# [[],[a],[b],[5],[X],[Y],[Z],[a,5],[b,5],[a,X],[a,Y],...,[b,5,Y],[b,5,Z]]
# note the order of elelemnts in each arry is immaterial (an array is
# considered an unordered set)
sub sets_aoa_to_subsets_aoa {
    my $aoa = shift // confess;

    if ( scalar( @{$aoa} ) == 0 ) {
        return [ [] ];
    }

    my $a           = shift @{$aoa};
    my $subsets_aoa = sets_aoa_to_subsets_aoa($aoa);
    my @new_subsets = ();
    foreach my $subset_a ( @{$subsets_aoa} ) {

        # leave subset as-is
        push @new_subsets, $subset_a;

        # add one element from $a
        foreach my $e ( @{$a} ) {
            push @new_subsets, [ $e, @{$subset_a} ];
        }
    }
    return \@new_subsets;

}

但是，我想对子集的大小添加一个限制。例如，如果我设置 max_size=2 那么最后四个解决方案将被忽略。我不能简单地生成所有解决方案然后过滤那些太大的解决方案，因为有时我有超过 100 个集合，每个集合有 2-3 个元素，而 2^100 不是一个很好的数字来处理，特别是当我只想要的子集时5 码或更小。

Answer 1

正如我所怀疑的，正则表达式适用于此。

具体解决方案

这里是针对所提出问题的具体解决方案。有 80 个答案。

my %seen;

"xy=a=12" =~ m{
        [^=]* (x|y)* [^=]*
    =
        [^=]* (a)*   [^=]*
    =
        [^=]* (1|2)* [^=]*

    (?{ 
         my $size = grep { length } $1, $2, $3;
         print "<$1> <$2> <$3>\n"
            if $size >= 1 && 
               $size <= 2 &&
             ! $seen{$1,$2,$3}++;
    })
    (*FAIL)
}x;

运行传输到 cat -n 的命令，您将看到 80 个答案。

当然，您会想要通用化和可扩展的东西，以便您可以将它应用到您的一百套情况中。制定一个通用的解决方案总是比制定一个特定的解决方案需要更长的时间，所以我会致力于这种概括，并在它看起来不错时尽快回复你。

通用解决方案

这是一般的解决方案；这不是我最漂亮的作品，但它确实有用:

#!/usr/bin/perl

use 5.010;
use strict;
use warnings;

our($MIN_PICK, $MAX_PICK) = (1, 2);

our @List_of_Sets = (
    [ qw[ x y ] ],
    [ qw[ a   ] ],
    [ qw[ 1 2 ] ],
);

sub dequeue($$) {
    my($leader, $body) = @_;
    $body =~ s/^\s*\Q$leader\E ?//gm;
    return $body;
}

################################

my $gunk     = " (?&gunk) ";
my $alter_rx = join("\n\t(?&post)\n" => map {
                  " $gunk ( "
                . join(" | " => map { quotemeta } @$_)
                . " ) * $gunk "
              } @List_of_Sets);
##print "ALTER_RX <\n$alter_rx\n>\n";

my $string = join(" = ", map { join(" ", @$_) } @List_of_Sets);
##print "STRING: $string\n";

my $numbers_list    = join(", " => map {  '$' . $_        } 1 .. @List_of_Sets);
my $numbers_bracket = join(" "  => map { '<$' . $_  . '>' } 1 .. @List_of_Sets);

my $print_statement = dequeue "|QQ|" => <<"PRINT_STATEMENT";

    |QQ|
    |QQ|    (?{
    |QQ|        no warnings qw(uninitialized);
    |QQ|        my \$size = grep { length } $numbers_list;
    |QQ|        print "$numbers_bracket\\n"
    |QQ|            if \$size >= $MIN_PICK &&
    |QQ|               \$size <= $MAX_PICK &&
    |QQ|             ! \$seen{$numbers_list}++;
    |QQ|    })
    |QQ|

PRINT_STATEMENT   
## print "PRINT $print_statement\n";

my $search_rx = do {
    use re "eval";
    my %seen;
    qr{
        ^
    $alter_rx
        $

    $print_statement

        (*FAIL)

        (?(DEFINE)
            (?<post>   =    )
            (?<gunk> [^=] * )
        )
    }x;
};
## print qq(SEARCH:\n"$string" =~ $search_rx\n);

# run, run, run!!
$string =~ $search_rx;

我有点担心您希望从中获得多少可能性。可能你应该把我上面概述的这个过程放在管道的另一端，这样你就可以从中读取任何你想要的内容，然后挂断电话，可以这么说，当你读完后.

我意识到这是一个相当不寻常的解决方案；我的代码经常是。 :)

我只是认为您不妨让正则表达式回溯的详尽排列性质为您完成这项工作。

也许其他人会拿出 Some::Abstruse::Module 来为您完成这项工作。你只需要权衡一下你喜欢哪个。

编辑:提高易读性、处理重复项和额外的最小/最大标准。