Wie kann ich alle Teilmengen einer Liste in Perl generieren?

Question

Ich habe einen mathematischen Satz in einem Perl-Array: (1, 2, 3). Ich würde gerne alle Untermengen dieses Satzes finden: (1), (2), (3), (1,2), (1,3), (2,3).

Mit 3 Elementen ist das nicht zu schwierig, aber wenn es 10 Elemente hat, wird das schwierig.

Gedanken?

Answer 1

Siehe Data::PowerSet, http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html usw.

Answer 2

Sie Data::PowerSet wie Matthew erwähnt verwenden können. Wenn Sie jedoch, wie in Ihrem Beispiel angegeben, nur richtige Teilmengen und nicht jede Teilmenge möchten, müssen Sie ein wenig mehr Arbeit erledigen.

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

Ebenso, wenn Sie die Nullmenge weglassen wollen, fügen Sie einfach den min Parameter:

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

Andernfalls alle Untergruppen zu erzielen, lassen Sie nur die beiden Parameter:

# result: every subset. 
    my $values = Data::PowerSet->new(68, 22, 43); 

Answer 3

Verwenden Sie Algorithm::ChooseSubsets.

Answer 4

Da Sie "mathematisches Set" sagen, nehme ich an, Sie meinen, dass es keine Duplikate gibt.

Eine naive Implementierung, die für bis zu 32 Elemente funktioniert:

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

(Für die vollständige Auswahl von Untergruppen, Schleife von 0 bis (1 < < @ Satz $) -1; ausgenommen 0 schließt die null Set (1 < @ < @ $ set) -1 schließt das ursprüngliche Set aus.)

Update: Ich befürworte dies nicht über ein Modul, nur vorschlägt es, falls Sie schauen, um zu verstehen, wie man vorgeht so ein Problem. Im Allgemeinen wird jedes Element entweder von einer gegebenen Teilmenge eingeschlossen oder ausgeschlossen. Sie möchten ein Element auswählen und zuerst alle möglichen Untermengen der anderen Elemente generieren, ohne das ausgewählte Element und dann alle möglichen Untergruppen der anderen Elemente einschließlich des ausgewählten Elements. Wenden Sie dies rekursiv auf das "Generiere alle möglichen Teilmengen" an. Verwerfen Sie schließlich die Null-Teilmenge und die nicht-richtige Teilmenge. Im obigen Code wird jedem Element ein Bit zugewiesen. Zuerst werden alle Subsets mit dem High-Bit an, dann alle damit ausgeschaltet. Für jede dieser Alternativen werden Teilmengen zuerst mit dem nächst-höchsten Bit aus und dann erst erzeugt. Wenn Sie so weitermachen, bis Sie nur am niedrigsten Bit arbeiten, erhalten Sie alle möglichen Zahlen in der richtigen Reihenfolge.

Answer 5

Wenn Sie wollen ein vorhandenes Modul nicht verwenden oder nicht, dann können Sie einfach Ihre eigene Teilmenge Erzeugungsalgorithmus Code ein bit-mask and a binary counter verwenden. Beispielcode folgt -

#!/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; 
} 

Anmerkung: Ich habe nicht vermocht, den Code zu testen, können einige Fehler müssen ausgebügelt werden.

Answer 6

Es ist ein Zählproblem - für N Elemente gibt es genau 2^N Untergruppen, und Sie haben von 0 bis 2^N zählen - 1 binär, sie alle aufzuzählen.

Für zB 3 Elemente gibt es 8 mögliche Untergruppen: 000, 001, 010, 011, 100, 101, 110 und 111 - die Nummern zeigen an, welche Mitglieder vorhanden sind.