Generarea permutărilor


Editat de Candale Silviu (silviu) la data 2019-11-03

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;
}

Observații

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, prin revenirea din apelul recursiv

Observații:

  • generarea valorilor din vectorul soluție începe cu primul element al acestuia; î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.

O soluție îmbunătățită

Analizând soluția de mai sus, constatăm că funcția OK() se apelează de foarte multe ori, pentru a verifica dacă valoarea lui x[k] nu apare deja în vectorul soluție. Putem evita utilizarea acestei funcții dacă folosim un vector caracteristic (uz[]) prin intermediul căruia să știm dacă o anumită valoarea i apare sau nu în vectorul soluție:

$$ uz[i]=\begin{cases}1 & \text{, dacă } i \text{ apare in } x[] \\ 0 & \text{, dacă } i \text{ nu apare in } x[]\end{cases} $$

În acest caz, soluția C++ devine:

#include <iostream>
using namespace std;

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

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

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

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;
}

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0123 - Permutari 11 ușoară fișiere
2 #0124 - Permutari1 11 ușoară fișiere
3 #0125 - Permutari2 11 medie fișiere
4 #1327 - SirPIE 11 medie fișiere
5 #0194 - Anagrame1 11 medie fișiere
6 #0202 - PermPF 11 medie fișiere
7 #0205 - Shuffle 11 medie fișiere
Editat de Candale Silviu (silviu) la data 2019-11-03