#!/usr/bin/perl
# Autor: Crian
# RDW 02 - Berechnung der Potenzmenge einer Menge
# Variante 2

use strict;
use warnings;


my $A = [ 'a', 'b', 'c', 'd', 'e' ];
my $P = P($A);
print_A_und_P($A, $P);


sub print_A_und_P {
    my ($A, $P) = @_;

    print "A = {", join(', ', @$A), "}\n";
    print "P(A) = {\n";
    for my $p (@$P) {
        print "         {", join(', ', @$p), "},\n";
    }
    print "       }\n";
}


sub P {
    my ($A) = @_;
    my $P   = [[]];
    my $N   = scalar @$A;

    # In jedem Schleifendurchlauf der folgenden for-Schleife wird
    # die Menge der $n elementigen Mengen aus $N Elementen gebildet:
    for my $n (1..$N) {
        # $n Elemente aus $N Elementen auswaehlen:
        my @Mengen; # Menge mit Nummermengen
        for my $element (1..$n) {
            # Moegliche Nummern fuer Element $element belegen:
            my @M = $element-1 .. $N-($n-$element)-1;

            # Bei einelementigen Mengen: Mengen mit nur diesem Element
            # erzeugen:
            unless (@Mengen) {
                push @Mengen, [ $_ ] for @M;
            }

            # Anderenfalls: Jede bisherige Nummernmenge aus @Mengen
            # vervielfachen und an jede Kopie eine der neuen
            # moeglichen Nummern anhaengen:
            else {
                my @TM = @Mengen;
                @Mengen = ();
                for my $tm (@TM) {
                    for my $m (@M) {
                        unless (grep { $_ >= $m } @$tm) {
                            push @Mengen, [ @$tm, $m ];
                        }
                    }
                }
            }
        }

        # Umsetzen der Nummern auf die Elemente der Menge
        # und Abspeichern der sich ergebenden Mengen:
        for my $menge (@Mengen) {
            push @$P, [ map { $_ = $A->[$_] } @$menge ];
        }
    }

    return $P;
}