Cerinţa

Se citeşte un număr natural nenul n şi o permutare a mulţimii M={1,2,..,n}. Să se afişeze, în ordine lexicografică, toate permutările mulţimii M care nu conţin elemente alăturate care au fost alăturate şi în permutarea dată.

Date de intrare

Fişierul de intrare shuffle.in conţine pe prima linie numărul n, iar pe a doua linie n valori distincte cuprinse între 1 și n, separate prin câte un spațiu, reprezentând permutarea dată.

Date de ieşire

Fişierul de ieşire shuffle.out va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu.

Restricţii şi precizări

• 0 < n < 9
• dacă nu există soluţii se va afişa pe prima linie a fişierului de ieşire mesajul nu exista

Exemplu

shuffle.in

4
2 3 1 4

shuffle.out

1 2 4 3 
3 4 2 1 

#include <bits/stdc++.h>

using namespace std;

ifstream cin("shuffle.in");
ofstream cout("shuffle.out");

int n, s[10] , p [10] , c1[10] , c2[10] , a[10] , cnt;

void afis()
{
    for(int i = 1 ; i <= n ; i++)
        cout << s[i] << " ";
    cout << '\n';
    cnt++;
}
void back(int k)
{
    for(int i = 1 ; i <= n  ; i++)
        if(p[i] == 0 && s[k - 1] != c1[i] && s[k - 1] != c2[i])
        {
            p[i] = 1;
            s[k] = i;
            if(k == n) afis();
            else back(k + 1);
            p[i] = 0;
        }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    a[0] = -1;
    a[n + 1] = -1;
    for(int i = 1 ; i <= n ; i++)
    {
        c1[a[i]] = a[i - 1];
        c2[a[i]] = a[i + 1];
    }
    back(1);
    if(cnt == 0) cout << "nu exista";
    return 0;
}