Articole

Citiți mai întâi Metoda backtraking

Prin permutare a unei mulțimi înțelegem o aranjare a elementelor sale, într-o anumită ordine. Este cunoscut, printre altele, faptul că numărul de permutări ale unei mulțimi cu n elemente este \(P_n = n! = 1 \cdot 2 \cdot \cdot \cdots \cdot n \). Prin convenție, \(P_0 = 0! = 1\).

Problema

Fie un număr natural n. Să se afișeze, în ordine lexicografică, permutările mulțimii \( \left\{ 1, 2, , \cdots , n \right\}\).

Exemplu

Pentru n=3, se va afișa:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Rezolvare

Bineînțeles, vom rezolva problema prin metoda backtracking. Vectorul soluție x[] va reprezenta o permutare candidat. Să ne gândim care sunt proprietățile unei permutări, pe care le va respecta și vectorul x[]:

• elementele sunt numere naturale cuprinse între 1 și n;
• elementele nu se repetă;
• vectorul x[] se construiește pas cu pas, element cu element. El va conține o permutare validă când va conține n elemente, desigur corecte.

Cele observate mai sus ne permit să precizăm condițiile specifice algoritmului backtracking, într-un mod mai formal:

• condiții externe: \( x[k] \in \left\{ 1,2, \cdots, n \right\} \);
• condiții interne: \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \cdots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \cdots, n \right \} \)
• condiții de existență a soluției: \(k = n\)

Sursă C++

Următorul program afișează pe ecran permutările, folosind un algoritm recursiv:

#include <iostream>
using namespace std;

int x[10] ,n;

void Afis()
{
    for( int j=1;j<=n;j++)
        cout<<x[j]<<" ";
    cout<<endl;
}

bool OK(int k){
    for(int i=1;i<k;++i)
        if(x[k]==x[i])
            return false;
    return true;
}

bool Solutie(int k)
{
    return k == n;
}

void back(int k){
    for(int i=1 ; i<=n ; ++i)
    {
        x[k]=i;
        if( OK(k) )
            if(Solutie(k))
                Afis();
            else
                back(k+1);
    }
}
int main(){
    cin>>n;
    back(1);
    return 0;
}

Semnificația funcțiilor

• void Afis(); afișează soluția curentă. Când se apelează, vectorul soluție x are n elemente, reprezentând o permutare completă;
• bool OK(int k); verifică condițiile interne. La apel, x[k] tocmai a primit o valoare conform condițiilor externe. Prin funcția OK() se va verifica dacă această valoare este validă;
• bool Solutie(int k); verifică dacă avem o soluție completă. Acest lucru se întâmplă când permutarea este completă – am dat o valoare corectă ultimului element al tabloului, x[n], adică atunci când k=n;
• void back(int k); – apelul acestei funcții dă valori posibile elementului x[x] al vectorului soluție și le verifică:
  • se parcurg valorile pe care le pot lua elementele vectorului, conform condițiilor externe (în acest caz, 1..n);
    • se memorează în x[k] valoarea curentă;
    • dacă valoarea lui x[k] este corectă, conform condițiilor interne, se verifică dacă avem o soluție completă. În caz afirmativ se afișează această soluție, în caz contrar se trece la următorul element, prin apelul recursiv;
  • la finalul parcurgerii, se revine la elementul anterior al vectorului x, prin revenirea din apelul recursiv.

Observații

• generarea valorilor din vectorul soluție începe cu primul element al acestuia, x[ 1 ]; în consecință, apelul principal al funcției back() este back(1);
• generarea permutărilor în ordine lexicografică se obține datorită faptului că, în funcția back() valorile posibile pe care le primește x[k] sunt parcurse în ordine crescătoare (for(int i=1 ; i<=n ; ++i)....). Dacă am fi parcurs valorile de la n la 1, s-ar fi generat permutările în ordine invers lexicografică;
• algoritmul este exponențial și poate fi folosit numai pentru valori mici ale lui n. O soluție ceva mai bună se poate obține dacă, pentru a stabili corectitudinea condițiilor interne, evităm parcurgerea elementelor deja memorate în vectorul soluție. Acest lucru poate fi realizat prin intermediul unui vector caracteristic, cu semnificația: v[p] = 1 dacă valoarea p face deja parte din permutare, și v[p]=0 dacă p nu face parte din permutare.

Varianta iterativă

În general, algoritmii nerecursivi sunt mai buni decât cei recursivi, deși uneori sunt mai dificil de urmărit. Următorul program iterativ afișează și el permutările pe ecran:

#include <iostream>

using namespace std;

int n , x[100];

void afisare(int k){
    for(int i = 1 ; i <= k  ; i ++)
       cout << x[i] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; i ++)
        if(x[i] == x[k])
            return 0;
    return 1;
}

void back()
{
    int k = 1;
    x[1] = 0;
    while(k > 0)
    {
        bool gasit = false;
        do{
            x[k] ++;
            if(x[k] <= n && OK(k))
                gasit = true;
        }
        while(! gasit && x[k ] <= n);
        if(! gasit)
            k --;
        else
            if(k < n)
            {
                k ++;
                x[k] = 0;
            }
            else
                afisare(k);

    }
}

int main(){
    cin >> n;
    back();
    return 0;
}

O variantă (puțin) mai bună

Algoritmul de generarea a permutărilor este unul exponențial, deci lent. Totuși, poate fi ușor îmbunățit în ceea ce privește verificarea condițiilor interne. Acestea cer ca valoarea curentă a lui x[k] (elementul care se generează) să nu se repete. În varianta anterioară am parcurs elementele care îl preced și le-am comparat cu x[k].

Această parcurgere poate fi evitată dacă folosim un vector caracteristic, uz[], cu următorul înțeles:

\(uz[v] = \begin{cases}
1& \text{dacă valoarea } v \text{ a fost plasată deja în vectorul soluție},\\
0& \text{dacă valoarea } v \text{ nu a fost plasată încă în vectorul soluție}
\end{cases} \)

Următoarele programe folosesc această idee. Primul respectă îndeaproape schema anterioară, în timp ce al doilea este mai scurt – verificarea condițiilor interne și a celor de existență a soluției făcându-se în în funcția back(), fără a mai scrie funcții de sine stătătoare:

#include <iostream>
using namespace std;

int x[10] , n , p, uz[10];

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    return uz[x[k]] == 0;
}

bool Solutie(int k)
{
    return k == n;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
        {
			uz[i] = 1;
            if(Solutie(k))
                Afis(k);
            else
                back(k + 1);
            uz[i] = 0;
        }
    }
}
int main(){
    cin >> n;
    back(1);
    return 0;
}

#include <iostream>
using namespace std;

int x[10] , n , p, uz[10];

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
        if(uz[i] == 0)
        {
		    x[k] = i;
		    uz[i] = 1;
		    if(k == n)
		        Afis(k);
		    else
		        back(k + 1);
		    uz[i] = 0;
        }
}
int main(){
    cin >> n;
    back(1);
    return 0;
}

Probleme propuse

Permutari Permutari1 Permutari2 SirPIE Anagrame1 PermPF Shuffle

Citește și

• Prezentare generală

• Generarea aranjamentelor
• Generarea combinărilor
• Generarea submulțimilor