#include <iostream>
#include <fstream>
int st[20],k,n;
using namespace std;
//k va masura nivelul din stiva, iar n va fi numarul de elemente din multimea pe care se lucreaza... la permutari nivelul maxim va fi egal cu numarul de elemente din multime.

ifstream f("permutari.in");
ofstream g("permutari.out");

void init()
{ st[k]=0;
//subprogramul initializeaza pozitia k din stiva cu 0 la fiecare apelare
}

int succesor()
{
if(st[k]<n) //se verifica daca elementul de pe pozitia k din stiva este mai mic decat n
{st[k]++; //va creste cu 1;
return 1;}
else return 0;
}
//subprogramul returneaza 1 pentru a arata ca mai exista cel putin un succesor si 0 in caz contrar.
int valid()
//permutarea presupune elemente distincte pe stiva asa ca subprogramul valid are rolul de a verifica daca elementul pus la nivelul k a mai fost folosit la un nivel anterior.
{
int i;
for(i=1;i<k;i++) //se utilizeaza o instructiune de repetitie pentru a parcurge stiva pana la nivelul k-1
if (st[k]==st[i]) return 0; //se verifica daca elementul de la fiecare nivel in parte
return 1; //coincide cu cel de la nivelul k
}
int solutie()
{
if(k==n) return 1; //daca nivelul stivei a ajuns la n, nivelul maxim, atunci se va returna 1 ,
return 0;          //rezultand o solutie...in caz contrar se va returna 0
}
void tipar() //se parcurge stiva complet si se tiparesc elementele solutiei
{ int i;
for(i=1;i<=n;i++){g<<st[i]<<" ";}
g<<'\n';
}

void back()
{int ev,as;   // ev(este valid)=este o variabila care ia valoarea 1 in cazul in care elementul de pe pozitia k e valid si 0 in caz contrar; as(are succesor)=este o variabila care ia valoarea 1 in cazul in care elementul de pe pozitia k are succesor si 0 in caz contrar;
k=1;         //se initializeaza variabila k(nivelul) cu 1 indicand faptul ca formarea solutiei se incepe de la nivelul 1;
init();           //se apeleaza subprogramul init (*vezi subprogramul init);
while(k>0)          //cand k ia valoarea 0 se paraseste subprogramul;
{
do{
as=succesor();     //in variabila as se va pune valoarea ce rezulta din apelarea subprogramului succesor (*vezi subprogramul succesor);
if(as==1) ev=valid();    // daca elementul de pe nivelul k are succesor atunci se verifica daca e valid iar in variabila ev va intra valoarea ce rezulta din apelarea subprogramului 1 daca e valid si 0 in caz contrar (*vezi subprogramul valid)
}while(as==1&&ev==0);     //aceasta instructiune de repetitie se va efectua cat timp elementul de pe pozitia k are succesor si acesta nu e valid
if(as==1)                 //daca elementul de pe pozitia k are succesor se vor efectua urmatoarele instructiuni;
if(solutie()==1) tipar();    //daca nivelul k va ajunge la n inseamna ca s-a reusit crearea unei solutii si se va trece la tiparirea ei (*vezi subprogramele solutie si respectiv tipar)
else { k++; init(); }      //daca nivelul k nu a ajuns la n atunci solutia nu e completa deci se creste nivelul si se initializeaza cu 0 (*vezi subprogramul init)
else k--;                  //daca nu are succesor atunci nivelul scade ;
}
}

int main()
{

f>>n ; //se citeste nr de elemente din multime
back(); //apelam subprogramul back
return 1;

}