Generarea permutărilor


Editat de Candale Silviu (silviu) la data 2019-05-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.

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