Potenzmengen berechnen mit List::PowerSet

Potenzmengen (engl. Powerset) lassen sich mit dem CPAN-Modul List::PowerSet von Nik Clayton einfach berechnen.

powerset() und powerset_lazy()

List::PowerSet stellt zwei Funktionen, powerset() und powerset_lazy(), bereit.

powerset()

powerset() nimmt eine Liste (Menge) entgegen und gibt eine Referenz auf eine Liste von Referenzen auf Arrays zurück - jede Array Referenz enthält eine Teilmenge.

Beispiel:

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

use List::PowerSet qw/powerset/;

my @input_list = qw/ x y z /;

my $powerset = powerset(@input_list);

foreach my $ps (@$powerset) {
    print "[ @$ps ]\n";
}

Das Programm erzeugt folgende Ausgabe:

[ x y z ]
[ y z ]
[ x z ]
[ z ]
[ x y ]
[ y ]
[ x ]
[  ]

powerset_lazy()

powerset_lazy() nimmt, wie powerset(), eine Liste entgegen und liefert eine Referenz auf eine Subroutine zurück, die als Iterator verwendet werden kann. Bei jedem Aufruf des Iterators wird eine weitere Teilmenge als Referenz auf einen Array zurückgegeben.

powerset_lazy() bietet sich vor allem bei umfangreichen Listen an. Im Gegensatz zu powerset() werden nicht alle Teilmengen auf ein Mal berechnet, sondern lazy evaluiert.

Beispiel:

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

use List::PowerSet qw/powerset_lazy/;

my @input_list = qw/ x y z /;

my $ps_iterator = powerset_lazy( @input_list );

while ( my $set = $ps_iterator->() ) {

    # $set is the next powerset entry
    print "[ @$set ]\n";
}

Das Programm erzeugt folgende Ausgabe:

[ x y z ]
[ y z ]
[ x z ]
[ z ]
[ x y ]
[ y ]
[ x ]
[  ]

Siehe auch

• List::PowerSet
• Data::PowerSet
• Data::PowerSet::Hash
• Higher-Order Perl
• Famous Perl One-Liners Explained, Part III: Calculations
• perlreftut - Mark's very short tutorial about references
• perllol - Manipulating Arrays of Arrays in Perl
• Wikipedia: Potenzmenge
• Mathepedia: Potenzmenge
• mathe-lexikon.at: Potenzmenge