# PBinfo #3411 – Gaseste Permutarea – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dau două valori: \(P\) și \(N\) cu proprietatea că \(N <= P!\) ( adică \(N <= 1*2*3*…*P\) ). 
Construindu-se toate permutările valorilor \(1,2,… P\), în ordine lexicografică, să se afișeze a \(N\)-a permutare.

Permutările în ordine lexicografică sunt:

1,2,3,.... P-1, P
1,2,3,.... P, P-1
................
P, P-1,... 3,2,1
Date de intrare
Valorile \(P\) și \(N\) din enunț.

Date de ieșire
A \(N\)-a permutare din ordonarea lexicografică a permutărilor mulțimii de numere \({1,2,… P}\).

Restricții și precizări

\(2 ≤ P ≤ 19\)
\(1<= N <= P!\)

Exemplu:
Intrare

3 4
Ieșire

2 3 1
Explicație
Permutările în ordine lexicografică a mulțimii de numere \({1,2,3}\) sunt: \((1,2,3)\),\((1,3,2)\),\((2,1,3)\),\((2,3,1)\),\((3,1,2)\),\((3,2,1)\). A patra permutare este \((2,3,1)\).

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int P;
long long N;
long long fact[21];                   
int cifre[21] = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; // ce cifre au fost deja folosite (vor avea 0 pe pozitia lor)
int main()
{
    cin >> P >> N;
    fact[0]=1;
    for(int i=1; i<=P; i++)
        fact[i] = i*fact[i-1]; 
    for(int i=P; i>=1; i--)    
    {
        int idx=1;
        while(N > fact[i-1])
        {
            N -= fact[i-1];
            idx++;
        }
        int poz = 1;
        while (cifre[poz]==0) poz++;
        while (idx > 1)
        {
            while (cifre[poz]==0) poz++;
            idx--;
            poz++;
        }
        while (cifre[poz]==0) poz++;
        cifre[poz]=0;
        cout << poz << ' ';
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3411)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3411/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3411/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)