Cerința

Se citește un număr natural n (n<16). Afișați în ordine lexicografică toate permutările mulțimii {1,2,…,n} în care elementele pare sunt puncte fixe (nu își schimbă poziția).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.

Restricții și precizări

• 1 < n < 16

Exemplu

Intrare

5

Ieșire

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

Explicație

Se vor genera permutările în care 2 și 4 nu își modifică poziția.

#include <bits/stdc++.h>
using namespace std;

int n , m , x[30] , cnt , p[30];

int afisare()
{
    int pp = 1;
    for(int i = 1 ; i <= n ; i++)
        if(i % 2 == 0) cout << i << " ";
        else cout << x[pp++] << " ";
    cout << '\n';
}

void back(int k)
{
    for(int i = 1 ; i <= n ; i += 2)
    if(!p[i])
    {
        x[k] = i;
        p[i] = 1;
        if(k == cnt) afisare();
        else back(k + 1);
        p[i] = 0;

    }
}

int main()
{
    cin >> n;
    if(n % 2 == 0) cnt = n  / 2;
    else cnt = (n + 1) / 2;
    back(1);
    return 0;
}