Aufgabe

Es soll die Potenzmenge einer gegebenen Menge ermittelt werden.

Lösung in Delphi - Quelltext und Ausgabe

procedure TForm1.bPotenzmengeClick(Sender: TObject);
type
  TMenge  = set of char;
  TPMenge = array of TMenge;
const
  M  : TMenge = ['a','b','c','d'];
var
  PM  : TPMenge;
  i,n : integer;

  function MengeToString(M : TMenge) : string;
  var
    s : string;
    i : integer;
  begin
    s := '[';
    for i := 0 to 255 do
      if char(i) in M then s := s + char(i)+',';
    if M  [] then s := copy(s,1,Length(s)-1);
    s := s + ']';
    result := s;
  end;

  function erstesElement(M : TMenge) : char;
  var
    i        : integer;
    gefunden : boolean;
  begin
    i := 0; gefunden := false;
    while (i < 255) and (not gefunden) do
    begin
      Inc(i);
      gefunden := (char(i) in M);
    end;
    result := char(i);
  end;

  procedure ermittelePotenzmenge(M : TMenge; var PM : TPMenge);
  var
    Element : char;
    R       : TMenge;
    PM1     : TPMenge;
    n,i     : integer;
  begin
    Element := erstesElement(M);
    if Element = char(255)
    then
    begin
      SetLength(PM,1);
      PM[0] := [];
    end
    else
    begin
      R := M-[Element];
      ermittelePotenzmenge(R,PM1);
      n := Length(PM1);
      SetLength(PM,2*n);
      for i := 0 to n-1 do PM[i] := PM1[i];
      for i := n to 2*n-1 do PM[i] := PM1[i-n]+[Element];
      SetLength(PM1,0);
    end;
  end;

begin
  ermittelePotenzmenge(M,PM);
  mAusgabe.Lines.Add('Menge = '+MengeToString(M));
  mAusgabe.Lines.Add(' ');
  mAusgabe.Lines.Add('Potenzmenge enthält:');
  mAusgabe.Lines.Add(' ');
  n := Length(PM);
  for i := 0 to n-1 do
    MAusgabe.Lines.Add(MengeToString(PM[i]));
end;

potenzmenge.zip

Lösung in Prolog - Quelltext und Ausgabe

powerset([],[[]]).
powerset([E|R],PM):-powerset(R,PMohneE),
                    findall([E|T],member(T,PMohneE),PMmitE),
                    append(PMohneE,PMmitE,PM).

Lange Listen gibt SWI-Prolog gekürzt aus. Nach Eingabe von "w" sieht man die ganze Liste.

?- powerset([a,b,c,d],PM).

PM = [[], [d], [c], [c, d], [b], [b, d], [b, c], [b|...], [...]|...] w[write]

PM = [[], [d], [c], [c, d], [b], [b, d], [b, c], [b, c, d], [a], [a, d], [a, c], [a, c, d],
      [a, b], [a, b, d], [a, b, c], [a, b, c, d]]

weiteres Beispiel

Baum des Pythagoras