Backtracking in combinatorica

Backtracking in combinatorica

1. Generarea permutarilor

1.1. Enuntul si consideratii

Problema: Sa se determine toate permutarile multimii .

Rezolvare: Notam cu (x[1], x[2], , x[n]) elementele permutarii pe care o cautam. Atunci,

89

aplicand lema bijectiei pe multimi finite , rezulta ca este necesar si suficient ca elementele
vectorului x sa fie doua cate doua distincte sau daca aplicam serializarea obtinem ca e suficient sa
testam ca valoarea nou introdusa in vectorul de solutii partiale este diferita de cele deja anterior
introduse.

1.2. Programul in limbajul Pascal

program generare_permutari;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k do
if x [i] x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], writeln
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level + 1, np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] := 0;
while k > 0 do
begin
repeat

inc (x [k]);

ok := fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr (1, np, p, x);
iterativ: bt (np, p, x)
end
end; var i: indicesir;
begin

writeln ('Generarea permutarilor pentru ( 1 2 n

write ('n=');

readln (np);

for i := 1 to np do

p [i] np;
backtracking (iterativ, np, p)
end.

1.3. Programul in limbajul C

include <stdio.h>

define MAXSIR

define RECURSIV

define ITERATIV

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k-- ;

void backtracking (int tip, int np, int p[])

void main ()

1.4. Exercitii si probleme

Demonstrati ca numarul de permutari generate este n!

Modificati programul astfel incat sa verificati ca numarul de permutari generat este n!

1.5. Rezolvarea exercitiilor si problemelor

se va construi un vector PSI de numere intregi, iar apoi in subprogramul de prelucrare a solutiei
se va afisa in loc de x[i] valoarea psi[x[i]].

se va construi un vector PSI de numere reale, iar apoi in subprogramul de prelucrare a solutiei se
va afisa in loc de x[i] valoarea psi[x[i]].

se va construi doi vectori PSI1 si PSI2 de numere reale , iar apoi in subprogramul de prelucrare
a solutiei se va afisa in loc de x[i] valoarea 'psi1[x[i]] + psi2[x[i]] * i'.

se va construi un vector PSI de siruri de caractere, iar apoi in subprogramul de prelucrare a
solutiei se va afisa in loc de x[i] valoarea psi[x[i]].

Prin inductie dupa n.

Se va folosi tehnica de numarare a solutiilor, iar apoi se va compara cu rezultatul inmultirii 1.2n.

2. Generarea combinarilor

2.1. Enuntul si consideratii

Problema: Sa se determine toate combinarile de cate n elemente ale multimii .

Rezolvare: Notam cu (x[1], x[2], , x[n]) elementele combinarii pe care o cautam. Pentru a

93

identifica in mod unic o combinare o vom retine scrisa in ordine crescatoare , adica:

(1) 1<=x[1]<x[2]<<x[n]<=m

Teorema: Conditia necesara si suficienta ca elementele vectorului x sa fie componentele unei

combinari scrise in ordine crescatoare este (1).

Demonstratie:

necesitatea: elementele vectorului x sunt componentele unei combinari scrise in ordine
crescatoare, deci x[1]<x[2]<<x[n]. De asemenea, x[i] e , deci x[1]>=1 si x[n]<=m.

suficienta: presupunem prin absurd ca desi avem (1), nu avem o combinare scrisa in ordine
crescatoare.

Varianta 2.1: e o combinare care nu e in ordine crescatoare nu convine pentru ca
x[1]<x[2]<<x[n].

Varianta 2.2: nu e o combinare, fals, deoarece elementele vectorului sunt doua cate doua

distincte si din multimea .

Contradictie.

Prin urmare, (1) poate fi o buna functie de continuare. De asemenea, e de observat ca putem renunta
la testele de la capat, ele fiind prinse de elementele sirului p. Deci pentru functia 9 putem folosi cu
succes conditia ca vectorul x sa aiba elementele strict crescatoare, de unde imediat deducem ca
pentru functia de continuare putem folosi conditia ca vectorul solutiilor partiale sa aiba elementele
strict crescatoare.

2.2. Programul in limbajul Pascal

program generare_combinari;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do
if x [i] >= x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do
write (x [i],

writeln
end;

i backtracking implementarea recursiva j
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

ialgoritmul backtracking selectatj
case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)

end
end;

var i: indicesir;
begin

writeln ('Generarea combinarilor de m elemente pentru ( 1 2
n )');

write ('m=');
readln (np);
write ('n=');
readln (p[1]);
for i := 2 to np do
p [i] := p[1];
backtracking (iterativ, np, p)
end.

2.3. Programul in limbajul C

include <stdio.h>

define MAXSIR

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k == np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main

Exercitii si probleme

Determinati conditiile omega obtinute in urma serializarii.

Imbunatatiti implementarea functiei FI prin implementarea doar a conditiilor omega obtinute in
urma serializarii.

Aratati ca functia de continuare aleasa nu este cea mai buna functie de continuare.

Determinati cea mai buna functie de continuare.

Reimplementati functia FI folosind cea mai buna functie de continuare.

Demonstrati ca numarul de combinari generate este m! / (n! (m-n)!).

Rezolvarea exercitiilor si problemelor

o>i='adevarat', o>k='x[k]>x[k-1]', k>1.

codul sursa pentru functia FI:

i.     in limbajul Pascal

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do

if (x [i] >= x [k]) then
fi := false

end;

ii.       in limbajul C

// functia de continuare
int fi (int k, int x[])

for (int i i < k; i++)
if (x [i] >= x [k])
return FALSE;

return TRUE;

Demonstratia o putem face pe baza unui contraexemplu: n=3, m=5, k=2, x[1]=1, x[2]=5 si
FI(2,(1,5))='adevarat', dar nu putem construi o combinare pentru ca nu putem gasi x[3] cu
urmatoarele proprietati: 5=x[2]<x[3]<=m=5.

Pentru a obtine cea mai buna functie de continuare, trebuie sa fim convinsi ca la validarea lui
x[k] vom putea construi in final o solutie. Cum x[k]<x[k+1]<<x[n] rezulta ca e necesar ca
x[k]<=x[n]-(n-k). Dar cum, la limita x[n]<=m, avem ca x[k]<=m-n+k ca o conditie
suplimentara. Deoarece este evidenta si suficienta, avem:

0>i='x[1]<=m-n+1'

a>k='x[k]>x[k-1] AND x[k]<=m-n+k', k>1.

codul sursa pentru functia FI:

i.     in limbajul Pascal

function fi (k: indicesir; x: sir): boolean;
begin

if k = 1 then

fi := (x [1] <= m - n + 1)
else

fi := (x [k] > x [k - 1]) and (x [k] + np - k > p [1])

end;

ii.       in limbajul C

// functia de continuare

int fi (int k, int x[])

Se stie ca numarul aranjamentelor este de m! / (m-n)!. Cum la fiecare combinare ii corespund
n! aranjamente obtinute prin permutare rezulta ca numarul de combinari este (m! / (m-n)!) / n!.

3. Generarea aranjamentelor

3.1. Enuntul si consideratii

Problema: Sa se determine toate aranjamenentele de cate n elemente ale multimii
Rezolvare: Notam cu (x[1], x[2], , x[n]) elementele aranjamentului pe care il cautam. Conditia
necesara si suficienta ca elementele vectorului x sa formeze un aranjament este ca elementele
vectorului x sa fie 2 cate 2 distincte. Prin serializare obtinem functia omega:

Wk(xx,x ,.,xk) = A (xk<>xi)
1 <= i < k

3.2. Programul in limbajul Pascal

program generare_aranjamente;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k do
if x [i] x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], writeln
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;

begin

writeln ('Generarea aranjamentelor de m elemente pentru ( 1 2
n )');

write ('m=');
readln (np);
write ('n=');
readln (p[1]);
for i to np do
p [i] p backtracking (iterativ, np, p)
end.

3.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 1OO

define RECURSIV

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE l

define FALSE O

functia de continuare
int fi (int k, int x[])
i

for (int i i < k; i++)
if (x [i] x [k])
return FALSE;

return TRUE;
j

// prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie (int n, int x[])
i

for (int i i <= n; i++)
printf ('%d x[i]);

printf ('n');
j

backtracking implementarea recursiva
void btr (int level, int np, int p[], int x[])
i

if (level > MAXSIR)

return;
if (level == np + l)

prelucreaza_solutie (np, x);
else

for (int i i <= p [level]; i++)
i

x [level] = i;

if fi (level, x)

btr (level np, p, x);

void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p

void main ()

Exercitii si probleme

Ce se intampla in cazul m=n?

Demonstrati ca numarul aranjamente afisat de program este m! / (m-n)!

Rezolvarea exercitiilor si problemelor

Se genereaza permutarile.

Se demonstreaza prin inductie descrescatoare dupa n, incepand cu n=m.
4. Generarea combinarilor cu repetitie

4.1. Enuntul si consideratii

Problema: Sa se determine toate combinarile cu repetitie de cate n elemente ale multimii .

Rezolvare: Notam cu (x[1], x[2], , x[n]) elementele combinarii pe care o cautam. Pentru a
identifica in mod unic o combinare o vom retine scrisa in ordine crescatoare , adica:

(1) 1<=x[1]<=x[2]<=. ,.<=x[n]<=m.

Teorema: Conditia necesara si suficienta ca elementele vectorului x sa fie componentele unei

combinari scrise in ordine crescatoare este (1).

Demonstratie:

necesitatea: elementele vectorului x sunt componentele unei combinari scrise in ordine
crescatoare, deci x[1]<=x[2]<=<=x[n]. De asemenea, x[i] e , deci x[1]>=1 si
x[n]<=m.

suficienta: presupunem prin absurd ca desi avem (1), nu avem o combinare scrisa in ordine
crescatoare.

Varianta 2.1: e o combinare care nu e in ordine crescatoare nu convine pentru ca
x[1]<=x[2]<=. ,.<=x[n].

Varianta 2.2: nu e o combinare, fals, deoarece elementele vectorului sunt din multimea .

Contradictie.

Prin urmare, (1) poate fi o buna functie de continuare. De asemenea, e de observat ca putem renunta
la testele de la capat, ele fiind prinse de elementele sirului p. Deci pentru functia 9 putem folosi

cu succes conditia ca vectorul x sa aiba elementele crescatoare, de unde imediat deducem ca pentru
functia de continuare putem folosi conditia ca vectorul solutiilor partiale sa aiba elementele
crescatoare.

4.2. Programul in limbajul Pascal

program generare_combinari_cu_repetitie;

const maxsir = 1OO;

type indicesir = l..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

i dimensiunile multimilor Mi j

var p: sir;

var np: indicesir;

i functia de continuare j

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

if k = l then

fi := true
else

fi (x [k - 1] <= x [k])
end;

i prelucrarea unei solutii x de dimensiune n j
procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := l to n do

write (x [i], writeln
end;

i backtracking implementarea recursiva j
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + l then

prelucreaza_solutie (np, x)
else

for i := l to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea combinarilor cu repetitie de m elemente
pentru ( 1 2 n write ('m=');
readln (np);
write ('n=');
readln (p[1]);
for i to np do
p [i] p[1];
backtracking (iterativ, np, p)
end.

4.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()

4.4. Exercitii si probleme

Tinand cont ca x [k] >= x [k-1], modificati algoritmii BT si BTR pentru a optimiza cautarea prin
eliminarea verificarii valorilor de la 1 la x[k-1]-1 pentru x[k].

Daca notam CR (m, n) numarul combinarilor cu repetitie de n elemente din multimea avem ca CR (m, n) = CR (1, n-1) + CR (2, n-1) + + CR (m, n-1).

Cu notatia de mai sus, avem ca CR (m, n) = CR (m-1, n) + CR (m, n-1).

Demonstrati ca CR (m, n) = (m+n-1)! / (m! (n-1)!).

4.5. Rezolvarea exercitiilor si problemelor

1. Modificarile algoritmilor sunt:

i.     BT:

Subprogram bt (np, p, x)
k := 1
x [k] := 0

Cat Timp k > 0 Executa
Repeta

incrementeaza (x [k])
Pana Cand fi (k, x) or (x [k] > p [k])
Daca x [k] <= p [k] Atunci
Daca k = np Atunci

prelucreaza_solutie (np, x)
Altfel

incrementeaza (k)
; aici se modifica !!!
x [k] := x [k - 1]

Sfarsit Daca

Altfel

decrementeaza (k)

Sfarsit Daca

Sfarsit Cat Timp

Sfarsit Subprogram

ii.       BTR:

subprogram btr (level, np, p, x)
daca level = np + 1 atunci

apel prelucreaza_solutie (np, x)
altfel

; aici se modifica !!!
daca level = 1 atunci

inf := 1
altfel

inf := x [k] + 1
sfarsit daca

pentru i := inf, p [level] executa

x [level] := i;

daca fi (level, x) then

apel btr (level + 1, np, p, x)

sfarsit daca

sfarsit pentru
sfarsit daca
sfarsit subprogram

Presupunem ca combinare o scriem cu termenii in ordine crescatoare, atunci daca k este primul
termen , ceilalti n-1 termeni trebuie sa inceapa cu cel putin k. Prin urmare pentru primul
termen k corespund CR (m+1-k, n-1) variante de construire, adica:

CR (m, n) = CR (1, n-1) + CR (2, n-1) + + CR (m, n-1).

Pe baza formulei de la problema precedenta, facandu-l pe m sa fie m-1 obtinem:

CR (m-1, n) = CR (1, n-1) + CR (2, n-1) + + CR (m-1, n-1)

sau dupa introducerea lui CR (m-1, n) in formula de la problema precedenta pe primele m-1 pozitii
avem:

CR (m, n) = CR (m-1, n) + CR (m, n-1).

Se demonstreaza prin inductie dupa m si n, pornind de la premiza ca CR (1, n) = n, pentru n > 0,
respectiv problema precedenta pentru pasul de inductie .

5. Generarea partitiilor de dimensiune fixa ale unui intreg

Enuntul si consideratii

Problema: Sa se determine partitiile de lungime n ale unui numar natural m.
Rezolvare: Notam cu x[1], x[2], x[n] partitia lui m. In mod evident, avem ca

(x[1], x[2], , x[n]) = 'x[1] + x[2] + + x[n] = m'

Din deducem ca suma partiala a oricaror k elemente trebuie sa fie mai mica ca m, adica:

(1) x[1] + x[2] + + x[k] <= m.

Fiind o conditie necesara pentru indeplinirea lui rezulta ca (1) poate fi o conditie de continuare:

k(x[1], x[2], ,x[k]) = 'x[1] + x[2] + + x[k] <= m' pentru k<n
k(x[1], x[2], ,x[k]) = 'x[1] + x[2] + + x[k] = m' pentru k=n.

Programul in limbajul Pascal

program generare_partitii_de_lungime_fixa;
const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var s: word; i: indicesir;
begin
s

for i to k do

inc (s, x [i]);
if k np then

fi := (s p else

fi := (s <= p end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], writeln
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k]

while k > 0 do
begin
repeat

inc (x [k]);
ok := fi (k, x) or (x
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea partitiilor lui n de lungime m');
write ('m=');
readln (np);
write ('n=');
readln (p[1]);
for i to np do
p [i] p[1];
backtracking (iterativ, np, p)
end.

5.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi

int p [MAXSIR];
int np;

define TRUE

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])

if (k == np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main

5.4. Exercitii si probleme

Modificati procedura de afisare a solutiei astfel incat sa avem insiruiri de forma:

etc

Daca notam PF (m, n) numarul partitiilor lui m de lungime n, avem ca PF (m, n) = PF (1, n-1) +
PF (2, n-1) + + PF (m-1, n-1).

Cu notatia de mai sus, avem ca PF (m, n) = PF (m-1, n) + PF (m, n-1).

Demonstrati ca PF (m, n) = (m-1)! / (n! (m-n-1)!).

Aratati ca functia de continuare gasita nu este cea mai buna functie de continuare.

Determinati cea mai buna functie de continuare.

Reimplementati functia FI folosind cea mai buna functie de continuare.

Presupunand ca se pune conditia suplimentara ca partitiile sa fie distincte din punct de vedere al
aplicarii succesive a asociativitatii si comutativitatii , determinati si implementati cea mai
buna functie de continuare.

5.5. Rezolvarea exercitiilor si problemelor

1. Codul sursa este:

in limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

write (p [1], ' = x [1]);
for i := 2 to n do

write (' + ',x [i]);
writeln
end;

ii. in limbajul C:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

Presupunem ca suma (partitia lui m) o scriem cu termenii in ordine crescatoare, atunci daca k
este primul termen , ceilalti n-1 termeni trebuie sa aiba suma m-k. Prin urmare pentru primul
termen k corespund PF (m-k, n-1) variante de partitionare, adica:

PF (m, n) = PF (1, n-1) + PF (2, n-1) + + PF (m-1, n-1).

Pe baza formulei de la problema precedenta, facandu-l pe m sa fie m-1 obtinem:

PF (m-1, n) = PF (1, n-1) + PF (2, n-1) + + PF (m-2, n-1)

sau dupa introducerea lui PF (m-1, n) in formula de la problema precedenta pe primele m-2 pozitii
avem:

PF (m, n) = PF (m-1, n) + PF (m-1, n-1).

Se demonstreaza prin inductie dupa m, pornind de la premiza ca PF (1, 1) = 1 si PF (1, n) = 0,

1 07

pentru n > 1, respectiv problema precedenta pentru pasul de inductie .

Contraexemplu: n = 3, m = 5, k = 2, x[1] = 4, x[2] = 1, FI(2, (4, 1))='4 + 1 <= 5'='adevarat' si
nu putem construi nici o solutie din aceasta solutie partiala.

Presupunand ca avem solutia partiala x[1], x[2], , x[k], pentru a putea fi siguri ca ea
genereaza cel putin o solutie trebuie sa ne gandim ca suma acestor k termeni trebuie sa fie mai
mica decat m-(n-k). Deci cea mai buna functie de continuare este:

9_k(x[1], x[2], , x[k])='x[1]+x[2]++x[k]<=m-n+k'

Codul sursa este:

i.     in limbajul Pascal:

function fi (k: indicesir; x: sir): boolean;
var s: word; i: indicesir;
begin
s := 0;

for i := 1 to k do

inc (s, x [i]);
fi := (s <= p [1] - np + k)
end;

ii.       in limbajul C:

// functia de continuare

int fi (int k, int x[])

Pentru a fi siguri ca putem construi o solutie, trebuie sa avem pentru fiecare din cei n-k termeni
negasiti conditia: x[i]>=x[k], i>k. Prin urmare, suma partiala trebuie sa fie:

(2) x[1]+x[2]++x[k]<=m-x[k]*(n-k)

adica (2) este cea mai buna conditie de continuare.
Codul sursa este:

function fi (k: indicesir; x: sir): boolean;
var s: word; i: indicesir;
begin
s := 0;

for i := 1 to k do

inc (s, x [i]);
fi := (s <= p [1] - x [k] * (np - k))
end;

ii.       in limbajul C:

// functia de continuare

int fi (int k, int x[])

Generarea functiilor injective

1. Enuntul si consideratii

Problema: Determinati toate functiile injective f : .
Rezolvare: Fie x[i] = f(i), i=1,n. Din definitia injectivitatii deducem ca functia este:

n(x[1], x[2], , x[n]) = a (x[i]<>x[j])

1<=i<j<=n

Serializand, obtinem:

fflk(x[1], x[2], , x[k]) = a (x[i]<>x[k])

1<=i<k

2. Programul in limbajul Pascal

program generare_injectii;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir = array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

i dimensiunile multimilor Mi j

var p: sir;

var np: indicesir;

i functia de continuare j

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do
if x [i] = x [k] then
fi := false

end;

i prelucrarea unei solutii x de dimensiune n j
procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], writeln
end;

i backtracking implementarea recursiva j
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then

if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea injectiilor de la la ');
write ('n=');
readln (np);
write ('m=');
readln (p for i to np do
p [i] p backtracking (iterativ, np, p)
end.

3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[]]

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k == np)

prelucreaza_solutie (np, x);

else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()
la n');
printf ('n=');
scanf ('%d', &np);
printf ('m=');
scanf ('%d', &(p for (int i i <= np; i++)
p [i] p

backtracking (ITERATIV, np, p);

Exercitii si probleme

Demonstrati ca daca m < n, nu avem solutii.

Modificati programul pentru a introduce testul de la problema precedenta.

Demonstrati ca problema generarii functiilor injective este echivalenta cu problema generarii
aranjamentelor.

Rezolvarea exercitiilor si problemelor

Presupunem ca m < n si prin absurd f injectiva. Rezulta ca vom avea n imagini distincte . Dar
cum in mod natural avem ca IIm fl <= n, rezulta n <= n. Contradictie.

Codul sursa modificat pentru testul m >= n este:var i: indicesir;
begin

writeln ('Generarea injectiilor de la la ');

write ('n=');
readln (np);
write ('m=');
readln (p [1]);
for i := 2 to np do
p [i] := p [1];
if p [1] >= np then

backtracking (iterativ, np, p)
else

writeln ('nu sunt solutii!')

end.

ii.       in limbajul C:

void main

printf ('Generarea injectiilor de la la n');
printf ('n=');
scanf ('%d', &np);
printf ('m=');
scanf ('%d', &(p [1]));
for (int i = 2; i <= np; i++)
p [i] = p [1];
if (p [1] >= np)

backtracking (ITERATIV, np, p);
else

printf ('nu sunt solutii!n');

3. Evident, pe baza functiei 9 si a functiilor de continuare.
7. Generarea functiilor surjective

7.1. Enuntul si consideratii

Problema: Determinati toate functiile surjective f : .
Rezolvare: Fie x[i] = f(i), i=1,n. Din definitia surjectivitatii deducem ca functia este:

n(x[1], x[2], , x[n]) = 'N(n) = m'
unde am notat cu:

N(k) = I u I
1<=i<=k

pentru a urmari evolutia indicatorului N(k) vom demonstra urmatoarele leme:

Lema 1: Daca A finita atunci, IA u I - IAI e
Demonstratie:

Cazul 1: a e A. A u = A, deci IA u I - IAI = 0 e .

Cazul 2: a A. presupunem ca IAI = n, atunci evident ca IA u I = n + 1, deci IA u I - IAI = 1
e .

Lema 2: N(k) <= N(k+1) si in plus N(k+1)-N(k) e

Demonstratie: N(k+1)-N(k) e este imediata pe baza lemei 1. Deoarece 0 >= 0 si 1 >= 0,
rezulta ca N(k+1) - N(k) >= 0.

Prin urmare, avem urmatorul sir de inegalitati:

1 = N(1) <= N(2) <= <= N(n-1) <= N(n) = m

de unde putem deduce imediat cea mai buna functie de continuare:

k (x[1], x[2], , x[k]) = 'N(k)>=m-n+k'

7.2. Programul in limbajul Pascal

program generare_surjectii;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i, j: indicesir;
var nn: integer;
var ok: boolean;
begin
nn := 0;

for j := 1 to p [1] do
begin

ok := false;
for i := 1 to k do
if x [i] j then

ok := true;
if ok then
inc (nn)
end;

fi := (nn >= p [1] - np + k)
end;

i prelucrarea unei solutii x de dimensiune n j
procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], ' ');
writeln
end;

i backtracking implementarea recursiva j
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea surjectiilor de la la ');
write ('n=');
readln (np);
write ('m=');
readln (p for i to np do
p [i] p backtracking (iterativ, np, p)
end.

7.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

return (nn >= p np k);

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()
la n');
printf ('n=');
scanf ('%d', &np);
printf ('m=');
scanf ('%d', &(p for (int i i <= np; i++)
p [i] p

backtracking (ITERATIV, np, p);

7.4. Exercitii si probleme

Demonstrati ca daca m > n, nu avem solutii.

Modificati programul pentru a introduce testul de la problema precedenta.

Modificati functia de afisare astfel incat sa se afiseze rezultatele sub forma:

f(1) = 1
f(2) = 4

7.5. Rezolvarea exercitiilor si problemelor

1. Presupunem prin absurd ca f surjectiva, adica Im f = , adica IIm fl = m. Dar, IIm fl =
lf ()l <= n. Deci m <= n, contradictie.

2. Codul sursa este: var i: indicesir;
begin

writeln ('Generarea surjectiilor de la la ');
write ('n=');
readln (np);
write ('m=');
readln (p [1]);
for i := 2 to np do
p [i] := p [1];
if (p [1] <= np)

backtracking (iterativ, np, p)
else

writeln ('nu sunt solutii!')

end.

ii.       in limbajul C:

void main

printf ('Generarea surjectiilor de la la n');
printf ('n=');
scanf ('%d', &np);
printf ('m=');
scanf ('%d', &(p [1]));
for (int i = 2; i <= np; i++)
p [i] = p [1];
if (p [1] <= np)

backtracking (ITERATIV, np, p);
else

printf ('nu sunt solutii!n');

3. Codul sursa este:
i. in limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

writeln ('Functia este:');
for i := 1 to n do

writeln ('f(', i, ') =', x [i], ' ');
end;

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

8. Generarea functiilor bijective

8.1. Enuntul si consideratii

Problema: Determinati toate functiile bijective f : .

Rezolvare: Fie x[i] = f(i), i=1,n. Din lema bijectiilor pe multimi finite deducem ca functia este:

n(x[1], x[2], , x[n]) = a (x[i]<>x[j])

1<=i<j<=n

Serializand, obtinem:

fflk(x[1], x[2], , x[k]) = a (x[i]<>x[k])

1<=i<k

8.2. Programul in limbajul Pascal

program generare_bijectii;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do
if x [i] x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i to n do

write (x [i], ' ');
writeln
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea bijectiilor de la la

write ('n=');

readln (np);

for i := 1 to np do

p [i] np;
backtracking (iterativ, np, p)
end.

8.3. Programul in limbajul C

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k-- ;

void backtracking (int tip, int np, int p[]t

void main ()
la n');
printf ('n=');
scanf ('%d', &np);
for (int i = 1; i <= np; i++)
p [i] = np;

backtracking (ITERATIV, np, p);
}

8.4. Exercitii si probleme

Demonstrati ca problema generarii functiilor bijective este echivalenta cu problema generarii
permutarilor.

Modificati functia de afisare astfel incat sa se afiseze functia si apoi sa se afiseze inversa
functiei.

8.5. Rezolvarea exercitiilor si problemelor

Deoarece o permutare este prin definitie o bijectie.

Codul sursa este:

i.     in limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('Functia este:');
for i := 1 to n do

writeln ('f(', i, ') =', x [i], ' ');
writeln ('Inversa functiei este:');
for i := 1 to n do
for j := 1 to n do
if x [i] = j then

writeln ('f^A(-1)(', i, ') =', j, ' ');

end;

ii.       in limbajul C:

// prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie (int n, int x[])

printf ('Functia este:n');
for (int i = 1; i <= n; i++)

printf ('f(%d) = %d ', i, x[i]);
printf ('Inversa functiei este:n');
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (x [i] == j)

printf ('f^A(-1)(%d) = %d ', i, j);}