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
