/*
Rearanjari:
Sa consideram ca n persoane n <= 10 asezate pe un rand
de n scaune doresc sa-si schimbe locurile, astfel incat
nicio persoana sa nu mai stea pe scaunul pe care era
asezata initial. Scrieti un program care sa genereze toate
rearanjarile posibile.
*/
 
#include <iostream>
 
using namespace std;
 
int n, sol[100], used[100];
 
void display() {
  for(int i = 1; i <= n; ++i) printf("%d ", sol[i]);
  printf("\n");
}
 
 
void bkt(int k) {
        if(k > n) display();
 
        for(int i = 1; i <= n; i++)
          if(!used[i] && i!=k) {
            used[i] = 1; sol[k] = i; bkt(k+1);used[i] =0;
          }
 
}
 
int main(int argc, char const *argv[]) {
  n = 4;
  bkt(1);
  return 0;
}
 

LyoKUmVhcmFuamFyaToKU2EgY29uc2lkZXJhbSBjYSBuIHBlcnNvYW5lIG4gPD0gMTAgYXNlemF0ZSBwZSB1biByYW5kCmRlIG4gc2NhdW5lIGRvcmVzYyBzYS1zaSBzY2hpbWJlIGxvY3VyaWxlLCBhc3RmZWwgaW5jYXQKbmljaW8gcGVyc29hbmEgc2EgbnUgbWFpIHN0ZWEgcGUgc2NhdW51bCBwZSBjYXJlIGVyYQphc2V6YXRhIGluaXRpYWwuIFNjcmlldGkgdW4gcHJvZ3JhbSBjYXJlIHNhIGdlbmVyZXplIHRvYXRlCnJlYXJhbmphcmlsZSBwb3NpYmlsZS4KKi8KCiNpbmNsdWRlIDxpb3N0cmVhbT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgc29sWzEwMF0sIHVzZWRbMTAwXTsKCnZvaWQgZGlzcGxheSgpIHsKICBmb3IoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgcHJpbnRmKCIlZCAiLCBzb2xbaV0pOwogIHByaW50ZigiXG4iKTsKfQoKCnZvaWQgYmt0KGludCBrKSB7CiAgICAgICAgaWYoayA+IG4pIGRpc3BsYXkoKTsKCiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICAgICAgICBpZighdXNlZFtpXSAmJiBpIT1rKSB7CiAgICAgICAgICAgIHVzZWRbaV0gPSAxOyBzb2xba10gPSBpOyBia3QoaysxKTt1c2VkW2ldID0wOwogICAgICAgICAgfQoKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkgewogIG4gPSA0OwogIGJrdCgxKTsKICByZXR1cm4gMDsKfQo=