Generarea aranjamentelor

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