BKT Hub — Generare Permutări

Teorie

🔢 Ce este o permutare?

O permutare a unui șir este o reordonare a tuturor elementelor sale. Pentru n elemente există n! permutări distincte.

Exemplu pentru n=3:

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

📐 Formula

numărul total de permutări

n=3 → 3! = 3×2×1 = 6

n=4 → 4! = 4×3×2×1 = 24

n=5 → 5! = 120 | n=10 → 10! = 3.628.800

🔁 Despre Backtracking

Backtracking este un algoritm general de descoperire a tuturor soluțiilor unei probleme, bazat pe construirea incrementală a soluțiilor-candidat și abandonarea oricărui candidat parțial care nu poate duce la o soluție validă.

Exemplul clasic este problema reginelor: se plasează 8 regine pe o tablă de șah astfel încât niciuna să nu atace alta. Orice configurație parțială cu două regine ce se atacă este abandonată imediat.

Tehnica se poate aplica numai problemelor ce admit un concept de candidat parțial de soluție și un test rapid de validare. Când se poate aplica, BKT este mult mai rapid decât forța brută, eliminând dintr-un singur test un număr mare de candidați.

Backtrackingul stă la baza unor limbaje de programare logică (Icon, Planner, Prolog) și este util la rezolvarea problemelor de satisfacere a constrângerilor. Termenul a fost inventat de matematicianul american D. H. Lehmer în anii 1950.

📋 Vectorul soluție și mulțimile A_k

Soluția este un vector X = (x₁, x₂, …, x_n), unde fiecare componentă aparține unei mulțimi finite:

x_i ∈ A_i, i ∈ {1, 2, …, n}

A_k — mulțimea valorilor posibile pentru x_k — este finită și ordonată. De regulă A₁ = A₂ = … = A_n. BKT generează soluția completând X în ordinea x₁, x₂, …, x_n și întoarce toate soluțiile.

🗺️ Cum se proiectează un BKT?

Patru aspecte de definit înainte de a scrie codul:

1 Vectorul soluție

Câte componente și ce semnifică x_k.

2 Mulțimile A_k

Valorile posibile și limitele domeniului.

3 Condiții VALID

Când este acceptată valoarea x_k.

4 Condiție SOLUȚIE

Când vectorul X este complet.

⚙️ Funcțiile BKT — descriere detaliată

Pe baza celor 4 aspecte se scriu funcțiile apelate de algoritmul general, aplicabil tuturor problemelor BKT:

INIT(k)

Inițializează x_k cu valoarea dinaintea primei valori din A_k. La prima incrementare x_k++ devine primul element valid. Dacă A_k = {1..n} → x_k = 0.

EXISTA(k)

Verifică dacă mai există valori netestate în A_k (x_k nu a atins limita maximă). Returnează 1 (continuă) sau 0 (revenire).

VALID(k)

Verifică compatibilitatea lui x_k cu valorile plasate la 1..k−1. Dacă returnează 0, valoarea este respinsă și se trece la următoarea.

SOLUTIE(k)

Verifică dacă s-a obținut o soluție completă. Condiția clasică: k == n (toate cele n componente au fost completate).

TIPAR(k)

Afișează soluția: vectorul x₁, x₂, …, x_k. Bucla iterează i = 1..k inclusiv (nu 1..k−1).

📜 Algoritmul BCK — schema iterativă

Structura while se aplică tuturor problemelor BKT. Doar funcțiile se adaptează problemei concrete.

Pseudocod C++

void BCK() { int k = 1; INIT(k); while (k > 0) if (EXISTA(k)) { x[k] = x[k] + 1; if (VALID(k)) if (SOLUTIE(k)) TIPAR(k); else { k = k + 1; INIT(k); } } else k = k - 1; }

↓ Avansare

VALID=1, SOLUTIE=0 → k+1, INIT

↩ Revenire

EXISTA=0 → k−1 (backtrack)

🗂️ BKT Generalizat (în plan)

Când x_k are mai multe caracteristici (ex: coordonate 2D), se introduce variabila auxiliară d[k] și funcția VALPOS(k) care calculează x_k din d[k].

Pseudocod C++

void BCKG() { int k = 2; // k=1 = start fix INIT(k); while (k > 1) if (EXISTA(k)) { d[k]++; VALPOS(k); // x[k] din d[k] if (VALID(k)) if (SOLUTIE(k)) TIPAR(k); else { k++; INIT(k); } } else k--; }

BCK clasic

x[k] ∈ A_k, k pornește de la 1

BCKG generalizat

x[k] calculat din d[k], k pornește de la 2

💻 Cod C++ — Permutări BKT

💻 Cod C++

#include <iostream> using namespace std; int n, x[10], sol = 0; void INIT(int k) { x[k] = 0; } int EXISTA(int k) { if(x[k] < n) return 1; else return 0; } int VALID(int k) { for(int i = 1; i < k; i++) if(x[i] == x[k]) return 0; return 1; } int SOLUTIE(int k) { if(k == n) return 1; else return 0; } void TIPAR(int k) { int i; sol++; for(i = 1; i <= k; i++) cout << x[i] << " "; cout << endl << endl; } void BCK() { int k = 1; INIT(k); while(k > 0) if(EXISTA(k)) { x[k]++; if(VALID(k)) { if(SOLUTIE(k)) TIPAR(k); else { k++; INIT(k); } } } else k--; } int main() { cout << "n = "; cin >> n; BCK(); cout << "S-au generat " << sol << " permutari." << endl; return 0; }

Simulare interactivă — n = 3

n =

Viteză: 4×

Permutarea curentă

Disponibile

Apasă ▶ Rulează pentru a porni simularea

Pas: 0/0

Permutări găsite: 0 / 6

Permutări găsite

Nicio permutare găsită încă...

Generare de Permutări