Articole

Citiți mai întâi Generarea aranjamentelor!

Introducere

Consideram o mulțime cu A cu n elemente. Prin combinări de k elemente din A înțelegem submulțimile cu k elemente ale multimii A. Numărul acestor combinări este \(C_n^k = \frac{A_n^k}{P_k}\). Mai multe formule pentru calculul numărului de combinări pot fi găsite în acest articol.

Acest articol prezintă un algoritm backtracking pentru determinarea în ordine lexicografică a combinărilor de k elemente ale mulțimii A={1 , 2 , ... , n}, elemente dintr-o combinare fiind generate în ordine crescătoare. El poate fi adaptat pentru determinarea combinărilor de k elemente ale unei mulțimi oarecare de n elemente.

Deoarece în algoritmul recursiv general apare funcția Back() cu parametrul k, pentru a păstra notațiile din algoritm vom considera în continuare combinările de k elemente luate câte p.

Soluția 1

Condiții

Ca orice rezolvare cu algoritmul backtracking, începem prin a preciza semnificația vectorului soluție. Astfel, x[] reprezintă o combinare. În consecință, el va respecta următoarele condiții:

• elemenele vectorului sunt valori între 1 și n;
• elementele nu se repetă;
• elementele sunt ordonate crescător
• vectorul se completează element cu element. Când va avea p elemente, reprezintă o combinare completă, care urmează a fi afișată.

Formal, exprimăm proprietățile de mai sus astfel:

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

Observăm (din nou) că în verificarea condițiilor interne intervine doar elementul x[k] (cel care este verificat) și elementele deja generate (x[1], x[2], … , x[k-1]).

Observăm că aceste condiții sunt cele de la generarea aranjamentelor, la care se adaugă condiția internă legată de ordinea elementelor din vector. În consecință, programul va fi cel de la aranjamente, cu completarea funcției OK().

Sursa C++

#include <iostream>
using namespace std;

int x[10] , n , p;

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

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

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

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

Soluția 2

Rafinarea condițiilor

Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:

1. cele două condiții interne pot fi reduse la una singură. Dacă pentru fiecare \( k \) are loc relația \(x[k] > x[k-1]\) atunci are loc și condiția \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\);
   Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
   • condiții interne: \(x[k] > x[k-1]\), pentru \( k > 1 \)
   • condiții de existență a soluției: \(k = p\)
2. condiția internă poate fi transformată în condiție externă. Dacă \(x[k] > x[k-1]\) atunci valorile pe care le poate lua \(x[k]\) (condiții externe) sunt \( \left\{ x[k-1] + 1, \ldots, n \right\} \). Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ x[k-1] +1 , x[k-1] +2, \ldots, n \right\} \);
   • condiții interne: nu există
   • condiții de existență a soluției: \(k = p\)

Cazul \(k = 1\) este unul special. Valorile pe care le poate lua sunt \(\left\{ 1 , 2 , 3 , \ldots \right\} \). Pentru a fi condițiile externe de mai sus corecte în în acest caz, este necesară inițializarea x[ 0 ] = 0, înaintea începerii generării.

Sursă C++

#include <iostream>
using namespace std;

int x[10] , n , p;

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

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

Probleme

combinari combinari2 siruri SubmDiv cifre_c subimp2

Citește și

• Prezentare generală
• Generarea permutărilor
• Generarea aranjamentelor

• Generarea submulțimilor

Citiți mai întâi Generarea permutărilor!

Introducere

Considerăm o mulțime cu n elemente. Prin aranjamente de k elemente din acea mulțime înțelegem șirurile de k elemente din ea. Două șiruri diferă prin valorile elementelor sau prin ordinea acestora.

Numărul acestor șiruri este aranjamente de n luate câte k, adică \(A_n^k = n \cdot (n-1) \cdot \ldots \cdot(n – k +1) \).

Acest articol prezintă algoritmul de generare în ordine lexicografică a aranjamentelor de k elemente ale mulțimii {1, 2, ..., n}. El poate fi ușor modificat pentru a genera aranjamentele unei mulțimi cu elemente oarecare.

Metoda folosită va fi backtracking, varianta recursivă. Deoarece în algoritmul de generare folosit intervine variabila k, ca parametru al funcției Back(), vom considera în continuare aranjamentele de n elemente luate câte p.

Exemplu

Pentru n = 4 și p = 3 vom avea 4 * 3 * 2 = 24 de aranajamente. Lista completă a acestora este:

1 2 3		2 1 3		3 1 2		4 1 2
1 2 4		2 1 4		3 1 4		4 1 3
1 3 2		2 3 1		3 2 1		4 2 1
1 3 4		2 3 4		3 2 4		4 2 3
1 4 2		2 4 1		3 4 1		4 3 1
1 4 3		2 4 3		3 4 2		4 3 2

Condiții

În rezolvarea problemei intervine vectorul soluție, x[]. Acesta reprezintă un aranjament candidat, care va deveni la un moment dat un aranjament de p elemente complet. Proprietățile vectorului soluție sunt cele specifice aranjamentelor:

• elementele sunt din mulțimea dată, adică numere intre 1 și n;
• elementele nu se repetă;
• vectorul se completează element cu element. Când va avea p elemente, reprezintă un aranjament complet, care urmează a fi afișat.

Formal, exprimăm proprietățile de mai sus astfel:

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

Sursă C++

Următorul program afișează pe ecran aranjamantele de n alemente luate câte p, în ordine lexicografică, folosind un algoritm recursiv:

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; 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 == p;
}

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

Se poate observa că atât condițiile descrise mai sus, cât și algoritmul de generare sunt foarte asemănătoare cu cele de la generarea permutărilor.

Acest lucru se datorează faptului că, la ambele probleme, vectorii soluție identici în ceea ce privește conținutul: șiruri de elemente diferite cuprinse între 1 și n. Diferă numai lungimea lor – momentul când vectorul soluție x[] conține o soluție completă:

• la problema permutărilor un vector soluție final are n elemente (toate elementele mulțimii date, într-o anumită ordine);
• la problema aranjamentelor un vector soluție final are p elemente (p elemente dintre cele n ale mulțimii date, într-o anumită ordine).

La fel ca în cazul generării permutărilor, și pentru această problemă se pot scrie soluții iterative, precum și soluții în care verificarea condițiilor interne să se facă cu un vector caracteristic, evitându-se parcurgerile repetate ale vectorului soluție.

Probleme propuse

196 3159

Citește și

• Prezentare generală
• Generarea permutărilor

• Generarea combinărilor
• Generarea submulțimilor

Metoda backtracking poate fi folosită în rezolvarea a diverse probleme. Este o metodă lentă, dar de multe ori este singura pe care o avem la dispoziție!

Introducere

Metoda backtracking poate fi aplicată în rezolvarea problemelor care respectă următoarele condiții:

• soluția poate fi reprezentată printr-un tablou x[]=(x[1], x[2], ..., x[n]), fiecare element x[i] aparținând unei mulțimi cunoscute Ai;
• fiecare mulțime Ai este finită, iar elementele ei se află într-o relație de ordine precizată – de multe ori cele n mulțimi sunt identice;
• se cer toate soluțiile problemei sau se cere o anumită soluție care nu poate fi determinată într-un alt mod (de regulă mai rapid).

Algoritmul de tip backtracking construiește vectorul x[] (numit vector soluție) astfel:

Fiecare pas k, începând (de regulă) de la pasul 1, se prelucrează elementul curent x[k] al vectorului soluție:

• x[k] primește pe rând valori din mulțimea corespunzătoare Ak;
• la fiecare pas se verifică dacă configurația curentă a vectorului soluție poate duce la o soluție finală – dacă valoarea lui x[k] este corectă în raport cu x[1], x[2], … x[k-1]:
  • dacă valoarea nu este corectă, elementul curent X[k] primește următoarea valoare din Ak sau revenim la elementul anterior x[k-1], dacă X[k] a primit toate valorile din Ak – pas înapoi;
  • dacă valoarea lui x[k] este corectă (avem o soluție parțială), se verifică existența unei soluții finale a problemei:
    • dacă configurația curentă a vectorului soluție x reprezintă soluție finală (de regulă) o afișăm;
    • dacă nu am identificat o soluție finală trecem la următorul element, x[k+1], și reluăm procesul pentru acest element – pas înainte.

Pe măsură ce se construiește, vectorul soluție x[] reprezintă o soluție parțială a problemei. Când vectorul soluție este complet construit, avem o soluție finală a problemei.

Exemplu

Să rezolvăm următoarea problemă folosind metoda backtracking, “cu creionul pe hârtie”: Să se afișeze permutările mulțimii {1, 2, 3}.

Ne amintim că un șir de numere reprezintă o permutare a unei mulțimi M dacă și numai dacă conține fiecare element al mulțimii M o singură dată. Altfel spus, în cazul nostru:

• are exact 3 elemente;
• fiecare element este cuprins între 1 și 3;
• elementele nu se repetă.

Pentru a rezolva problemă vom scrie pe rând valori din mulțimea dată și vom verifica la fiecare pas dacă valorile scrise duc la o permutare corectă:

Formalizare

Pentru a putea realiza un algoritm backtracking pentru rezolvarea unei probleme trebuie să răspundem la următoarele întrebări:

1. Ce memorăm în vectorul soluție x[]? Uneori răspunsul este direct; de exemplu, la generarea permutărilor vectorul soluție reprezintă o permutare a mulțimii A={1,2,...,n}. În alte situații, vectorul soluție este o reprezentare mai puțin directă a soluției; de exemplu, generarea submulțimilor unei mulțimi folosind vectori caracteristici sau Problema reginelor.
2. Ce valori poate lua fiecare element x[k] vectorului soluție și câte elemente poate avea x[]? Altfel spus, care sunt mulțimile Ak. Vom numi aceste restricții condiții externe. Cu cât condițiile externe sunt mai restrictive (cu cât mulțimile Ak au mai puține elemente), cu atât va fi mai rapid algoritmul!
3. Ce condiții trebuie să îndeplinească x[k] ca să fie considerat corect? Elementul x[k] a primit o anumită valoare, în conformitate ce condițiile externe. Este ea corectă? Poate conduce la o soluție finală? Aceste condiții se numesc condiții interne și în ele pot să intervină doar x[k] și elementele x[1], x[2], …, x[k-1]. Elementele x[k+1], …, x[n] nu poti apărea în condițiile interne deoarece încă nu au fost generate!!!
4. Am găsit o soluție finală? Elementul x[k] a primit o valoare conformă cu condițiile externe, care respectă condițiile interne. Am ajuns la soluție finală sau continuăm cu x[k+1]?

Exemplu. Pentru problema generării permutărilor mulțimii \(A=\{1, 2, 3, …, n\}\), condițiile de mai sus sunt:

1. Vectorul soluție conține o permutare a mulțimii \( A \);
2. Condiții externe: \( x[k] \in \{1,2,3,…,n\} \) sau \( x[k] = \overline{1,n} \), pentru \( k = \overline{1,n} \)
3. Condiții interne: \( x[k]\neq x[i] \), pentru \( i = \overline{1,k-1} \)
4. Condiții de existență a soluției: \( k = n \)

Algoritmul general

Metoda backtracking poate fi implementată iterativ sau recursiv. În ambele situații se se folosește o structură de deate de tip stivă. În cazul implementării iterative, stiva trebuie gestionată intern în algoritm – ceea ce poate duce la dificulăți în implementăre. În cazul implementării recursive se folosește spațiu de memorie de tip stivă – STACK alocat programului; implementarea recursivă este de regulă mai scurtă și mai ușor de înțeles. Acest articol prezintă implementări recursive ale metodei.

Următorul subprogram recursiv prezintă algoritmul la modul general:

• la fiecare apel BACK(k) se generează valori pentru elementul x[k] al vectorului soluție;
• instrucțiunea Pentru modelează condițiile externe;
• subprogramul OK(k) verifică condițiile interne
• subprogramul Solutie(k) verifică dacă configurația curentă a vectorului soluție reprezintă o soluție finală
• subprogramul Afisare(k) tratează soluția curentă a problemei – de exemplu o afișează!

subprogram BACK(k)
    ┌ pentru fiecare element i din A[k] executa
    │    x[k] ← i
    │    ┌ daca OK(k) atunci
    │    │    ┌ daca Solutie(k) atunci
    │    │    │    Afisare(k)
    │    │    │ altfel
    │    │    │    BACK(k+1)
    │    │    └■
    │    └■
    └■
sfarsit_subprogram

Observații:

• de cele mai multe ori mulțimile \(A\) sunt de forma \( A=\{1, 2, 3, …. , n \} \) sau \( A=\{1, 2, 3, …. , m \} \) sau \( A=\{a, a + 1, a + 2, …. , b \} \) sau o altă formă astfel încât să putem scrie instrucțiunea Pentru conform specificului limbajului de programare folosit – eventual folosind o structură repetitivă de alt tip! Dacă este necesar, trebuie realizate unele transformări încât mulțimile să ajungă la această formă!
• elementele mulțimii \( A \) pot fi in orice ordine. Contează însă ordinea în care le vom parcurge în instrucțiunea Pentru, deoarece în probleme este precizată de obicei o anumită ordine în care trebuie generate soluțiile:
  • dacă parcurgem elementele lui \( A \) în ordine crescătoare vom obține soluții în ordine lexicografică;
  • dacă parcurgem elementele lui \( A \) în ordine descrescătoare vom obține soluții în ordine invers lexicografică.
• în anumite probleme determinarea unei soluții finale nu conduce la întreruperea apelurilor recursive. Un exemplu este generarea submulțimilor unei mulțimi. În acest caz algoritmul de mai sus poate fi modificat astfel:

       ┌ daca OK(k) atunci
       │    ┌ daca Solutie(k) atunci
       │    │     Afisare(k)
       │    └■
       │     BACK(k+1)
       └■

Bineînțeles, trebuie să ne asigurăm că apelurile recursive se opresc!

Un șablon C++

Următoarea secvență C++ oferă un șablon pentru rezolvarea unei probleme oarecare folosind metoda backtracking. Vom considera în continuare următoarele condiții externe: \( x[k] = \overline{A,B} \), pentru \( k = \overline{1,n} \). În practică \( A \) și \( B \) vor avea valori specifice problemei:

#include <fstream>
using namespace std;

int x[10] ,n;

int Solutie(int k){
    // x[k] verifică condițiile interne
    // verificare dacă x[] reprezintă o soluție finală
    return 1; // sau 0
}

int OK(int k){
    // verificare conditii interne
    return 1; // sau 0
}

void Afisare(int k)
{
    // afișare/prelucrare soluția finală curentă
}

void Back(int k){
    for(int i = A ; i <= B ; ++i)
    {
        x[k]=i;
        if( OK(k) )
            if(Solutie(k))
                Afisare(k);
            else
                Back(k+1);
    }
}
int main(){
    //citire date de intrare
    Back(1);
    return 0;
}

De multe ori condițiile de existență a soluției sunt simple și nu se justifică scrierea unei funcții pentru verificarea lor, ele putând fi verificate direct în funcția Back().

De cele mai multe ori, rezolvarea unei probleme folosind metoda backtracking constă în următoarele:

1. stabilirea semnificației vectorului soluție;
2. stabilirea condițiilor externe;
3. stabilirea condițiilor interne;
4. stabilirea condițiilor de existența a soluției finale;
5. completarea adecvată a șablonului de mai sus!

Complexitatea algoritmului

Algoritmii Backtracking sunt exponențiali. Complexitatea depinde de la problemă la problemă dar este de tipul \( O(a^n) \). De exemplu:

• generarea permutărilor unei mulțimi cu n elemente are complexitatea \( O(n!)\);
• generarea submulțimilor unei mulțimi cu n elemente are complexitatea \( O(2^n) \)
• produsul cartezian \( A^n\) unde mulțimea \( A=\{1,2,3,…,m\}\) are complexitatea \(O(m^n)\)
• etc.

PbInfo propune spre rezolvare cu metoda backtracking câteva zeci de probleme! SUCCES!

Citește mai departe

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

#include <iostream>
#include <cmath>
using namespace std;
int n,st¹⁰⁰¹;
void afis(int k)
{ for(int i=1; i<=k; i++) { for(int j=1; j<=k; j++) if(st[i]==j) cout<<“D”; else cout<<”*”; cout<<endl; } cout<<endl;
}
int valid(int k)
{ for(int i=1; i<k; i++) if(st[k]==st[i] || abs(st[i]-st[k])==abs(i-k)) return 0; return 1;
}
void backt(int k)
{ for(int i=1; i<=n; i++) { st[k]=i; if(valid(k)) if(k==n) afis(k); else backt(k+1); }
}
int main()
{ cin>>n; backt(1); return 0;
}

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

Problema:

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

Soluție:

Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare.

Metoda 1

În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente.

• semnificaţia vectorului soluție: x[] reprezintă la un moment dat o submulțime
• condiții externe: x[k] în {1,2,..,n}, k între 1 și n;
• condiții interne: x[k]>x[i], i între 1 și k-1. Deoarece condițiile interne se aplică pentru toate elementele vectorului soluție, este suficient ca x[k]>x[k-1], pentru k>1;
• condiții de existența a soluției: fiecare variantă a vectorului soluție corespunde cu o submulțime. Orice valoare validă plasată în vectorul soluție conduce la o soluție.

void afis(int k){
    for(int i=1 ; i<=k ; ++i)
        cout << x[i] << " ";
    cout << endl;
}
bool valid(int k){
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            afis(k);
            back(k+1);
        }
    }
}

Constatăm că putem rafina condițiile externe; deoarece x[k]>x[k-1], condițiile devin:

• Condiții externe: x[k] în {x[k-1]+1, ... , n}, k între 1 și n. Pentru a uniformiza algoritmul, considerăm de la început că x[0] = 0;
• Condiții interne: nu mai avem condiții interne; funcția valid() nu mai este necesară;
• Condiții de existența a soluției rămân aceleași.

void back(int k){
    for(int i=x[k-1]+1;i<=n;++i)
    {
        x[k]=i;
        afis(k);
        back(k+1);
    }
}

Să observăm că submulțimea vidă nu se regăsește printre soluțiile generate cu acest algoritm. Dacă este cazul, afișarea ei se poate face în afara algoritmului de generare.

Metoda 2

Această metodă se bazează pe observația că pentru fiecare submulțime a mulțimii date, {1,2,...,n} îi corespunde un șir de n biți, notat x[], astfel:

• dacă bitul x[k] = 0, elementul k nu aparține submulțimii curente;
• dacă bitul x[k] = 1, elementul k aparține submulțimii curente.

Reamintim că o mulțime cu n elemente are 2 n submulțimi.

Exemplificăm cu mulțimea {1,2,3,4}.

Putem să generăm toate șirurile de n biți, iar pentru fiecare șir să construim submulțimea corespunzătoare. Generarea șirurilor se poate face în mai multe moduri:

• parcurgem numerele de la 0 la 2n-1 și transformăm fiecare număr în baza 2; obținem astfel pentru fiecare număr un șir de biți care va fi transformat în submulțime;
• generăm direct șirul de biți cerut cu metoda backtracking.

Vom detalia mai jos rezolvarea cu backtracking:

• semnificaţia vectorului soluție: x[] conține la un moment dat un șir de biți care va corespunde unei submulțimi
• condiții externe: x[k] = 0 sau 1;
• condiții interne nu există. Orice configurație parțială a vectorului x[] va conduce la o soluție validă
• condiții de existență a soluției: k == n.

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

void back(int k){
    for(int i = 0; i <= 1 ; ++i)
    {
        x[k]=i;
        if(k == n)
            afis(k);
        else
            back(k+1);
    }
}

Probleme

SubmDiv Submultimi Siruri

Citește și

• Prezentare generală
• Generarea permutărilor
• Generarea aranjamentelor
• Generarea combinărilor