Cerinţa

Se numește permutare a unei mulțimi o aranjare a elementelor mulțimii în altă ordine. De exemplu, permutările mulțimii {1,2,3} sunt: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Fie (p1, p2, ..., pn) o permutare a mulțimii {1,2,...,n}. Se numește punct fix al permutării o valoare k din mulțime cu proprietatea că pk = k.

Scrieţi definiția completă a subprogramului C++ permutare care are 2 parametri: a, prin care primeşte un tablou unidimensional cu maximum 100 de numere naturale mai mici decât 1000 și n, numărul efectiv de elemente ale tabloului.

Subprogramul verifică dacă elementele vectorului a reprezintă o permutare fără puncte fixe a mulțimii {1,2,...,n} și returnează valoarea 1 în caz afirmativ, respectiv 0 în caz negativ.

Restricţii şi precizări

• 0 < n <= 100
• numele subprogramului cerut este permutare
• parametrii sunt, în această ordine: a, n, cu semnificația de mai sus
• elementele vectorului a sunt indexate de la zero

Exemplu

Dacă n=6 și a=(2,3,1,6,4,5) subprogramul va returna valoarea 1.

Dacă n=4 și a=(2,3,1,4) subprogramul va returna valoarea 0, deoarece permutarea are un punct fix.

Important

Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

int permutare(int a[] , int n)
{
    int cnt=0;
    int cn=0;
    int f[100000]={0};
    for(int i = 0 ; i < n ; ++i)
    {
        f[a[i]]++;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        if(f[i]==1)
            cn++;
    }
    for(int i = 0 ; i < n ; ++i)
    {
        if(a[i]==i+1)
            cnt++;
        if(a[i]>n)
            cn=0;
    }
    if(cnt==0 && cn==n)
        return 1;
    else
        return 0;
}