Generare Submulțimi

Aspecte teoretice:

În matematică, mai exact în teoria mulțimilor, se spune că mulțimea B este submulțimea mulțimii A dacă B „este conținută” de A. Echivalent, putem scrie , citit B include A, sau B conține A. Relația dintre mulțimi stabilită de se numește incluziune sau conținere.

Dacă A este o submulțime a lui B, dar nu este egală cu B, atunci A se numește submulțime proprie a lui B, ceea ce se scrie sau . Totuși, în literatură aceste simboluri se citesc la fel ca și , deci se preferă adesea să se folosească simbolurile mai explicite și și pentru incluziunea strictă.

Problemă:

Să considerăm că avem o mulţime A cu n elemente oarecare şi ne punem problema generării tuturor submulţimilor sale. Pentru aceasta, vom considera următorul mod de reprezentare a unei submulţimi a mulţimii iniţiale: se va folosi un vector x=(x[1], …, x[n]), cu elemente doar 1 şi 2.
Semnificaţia acestui vector este: x[k]=1, dacă elementul A[k] aparţine submulţimii curente generate, respectiv x[k]=2, dacă nu. De acest lucru va ţine cont procedura de afişare a soluţiilor rezultat Scrie. Să observăm că pentru a genera vectorii aceia cu elemente doar de 1 şi 2 este necesar să considerăm produsul cartezian al n mulţimi de forma {1,2}.

Implementare:

Cod Sursa PASCAL

 

program GenerareSubmultimi;
uses crt;
const max=10;
var i,k,n: Integer;
x: array[1..max] of Integer;
a: array[1..max] of String;
cont: Boolean;

procedure Scrie;
begin
WriteLn(‘O solutie este:’);
Write(‘{ ‘);
for i:=1 to n do
if x[i]=1 then
Write(a[i],’ ‘);
WriteLn(‘}’);
ReadLn
end;
begin
WriteLn(‘Generarea submultimilor unei multimi’);
WriteLn(‘************************************’);
Write(‘Dati nr de elemente: ‘); Readln(n);
for i:=1 to n do
begin
Write(‘Dati elementul al ‘,i,
‘-lea al multimii: ‘);
ReadLn(a[i])
end;
k:=1; x[k]:=0;
while k>0 do
begin
cont:=false;
while (x[k]<2) and (not cont) do
begin
x[k]:=x[k]+1;
cont:=True
end;
if cont=true then
if k=n then Scrie
else
begin
k:=k+1; x[k]:=0;
end
else
k:=k-1
end
end.