#include <stdio.h>
#define SIZE 100
int stack[SIZE],
level,
n,
k;
void init(){
stack[level] = 0;
};
int valid() {
int i;
for(i = 1; i < level; i++)
if(stack[i] == stack[level]) return 0;
return 1;
};
int succ() {
if(stack[level]<n){
stack[level]++;
return 1;
}
return 0;
};
int sol() {
return level == k;
};
void print() {
int i;
printf("x | ");
for(i = 1; i <= k; i++) printf("%d ", i);
printf("\n----------------\n");
printf("f(x) | ");
for(i = 1; i <= k; i++) printf("%d ", stack[i]);
printf("\n\n");
};
void bt() {
int hs,is;
level = 1;
while(level > 0) {
hs = 1; is = 0;
while(hs && !is) {
hs = succ();
if(hs) is = valid();
}
if(hs) {
if(sol()) print();
else {level++;init();}
} else level--;
}
};
void printSet(char set, int n, int flag) {
int i;
if( flag ) printf("f : A -> B\n\n");
printf("%c = {",set);
for(i = 1; i <= n; i++) {
printf("%d ",i);
}
printf("}\n\n");
};
int main() {
//freopen("genAllInjective.out","w",stdout);
printf("%s\n\n","Generating All The Injective Functions");
//f : A -> B
//A = {1,2}, B = {1,2,3}
scanf("%d",&n);
scanf("%d",&k);
printSet('A',k, 1);
printSet('B',n, 0);
bt();
return(0);
};
I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgU0laRSAxMDAKCmludCBzdGFja1tTSVpFXSwKICAgIGxldmVsLAogICAgbiwKICAgIGs7Cgp2b2lkIGluaXQoKXsKCiAgICAgc3RhY2tbbGV2ZWxdID0gMDsKfTsKCmludCB2YWxpZCgpIHsKCiAgICBpbnQgaTsKCiAgICBmb3IoaSA9IDE7IGkgPCBsZXZlbDsgaSsrKSAKCiAgICAgICAgaWYoc3RhY2tbaV0gPT0gc3RhY2tbbGV2ZWxdKSByZXR1cm4gMDsKCiAgICByZXR1cm4gMTsKfTsKCmludCBzdWNjKCkgewoKICAgIGlmKHN0YWNrW2xldmVsXTxuKXsKCiAgICAgICBzdGFja1tsZXZlbF0rKzsKCiAgICAgICByZXR1cm4gMTsgIAogICAgfQogICAgcmV0dXJuIDA7Cn07CgppbnQgc29sKCkgewoKICAgIHJldHVybiBsZXZlbCA9PSBrOyAKfTsKCnZvaWQgcHJpbnQoKSB7CgogICAgaW50IGk7CiAKICAgIHByaW50ZigieCAgICB8ICIpOwogICAgZm9yKGkgPSAxOyBpIDw9IGs7IGkrKykgcHJpbnRmKCIlZCAiLCBpKTsKICAgIHByaW50ZigiXG4tLS0tLS0tLS0tLS0tLS0tXG4iKTsKICAgIHByaW50ZigiZih4KSB8ICIpOwogICAgZm9yKGkgPSAxOyBpIDw9IGs7IGkrKykgcHJpbnRmKCIlZCAiLCBzdGFja1tpXSk7CiAgICBwcmludGYoIlxuXG4iKTsgICAgICAgICAgIAp9OwoKdm9pZCBidCgpIHsKCiAgICBpbnQgaHMsaXM7CgogICAgbGV2ZWwgPSAxOwoKICAgIHdoaWxlKGxldmVsID4gMCkgewoKICAgICAgICAgIGhzID0gMTsgaXMgPSAwOwogCiAgICAgICAgICB3aGlsZShocyAmJiAhaXMpIHsKCiAgICAgICAgICAgICAgICBocyA9IHN1Y2MoKTsKCiAgICAgICAgICAgICAgICBpZihocykgaXMgPSB2YWxpZCgpOyAgICAgICAgICAgICAgICAgICAKICAgICAgICAgIH0gCgogICAgICAgICAgaWYoaHMpIHsKCiAgICAgICAgICAgIGlmKHNvbCgpKSBwcmludCgpOwoKICAgICAgICAgICAgICAgIGVsc2Uge2xldmVsKys7aW5pdCgpO30gICAgICAgICAgICAgICAgCgogICAgICAgICAgfSBlbHNlIGxldmVsLS07ICAKICAgIH0KCn07Cgp2b2lkIHByaW50U2V0KGNoYXIgc2V0LCBpbnQgbiwgaW50IGZsYWcpIHsKCiAgICAgaW50IGk7CgogICAgIGlmKCBmbGFnICkgcHJpbnRmKCJmIDogQSAtPiBCXG5cbiIpOwoKICAgICBwcmludGYoIiVjID0geyIsc2V0KTsKCiAgICAgZm9yKGkgPSAxOyBpIDw9IG47IGkrKykgewoKICAgICAgICAgcHJpbnRmKCIlZCAiLGkpOyAgICAgICAgIAogICAgIH0KCiAgICAgcHJpbnRmKCJ9XG5cbiIpOwp9OwoKaW50IG1haW4oKSB7CgogICAgLy9mcmVvcGVuKCJnZW5BbGxJbmplY3RpdmUub3V0IiwidyIsc3Rkb3V0KTsKCiAgICBwcmludGYoIiVzXG5cbiIsIkdlbmVyYXRpbmcgQWxsIFRoZSBJbmplY3RpdmUgRnVuY3Rpb25zIik7CiAgICAvL2YgOiBBIC0+IEIKICAgIC8vQSA9IHsxLDJ9LCBCID0gezEsMiwzfQogICAgc2NhbmYoIiVkIiwmbik7CiAgICBzY2FuZigiJWQiLCZrKTsKCiAgICBwcmludFNldCgnQScsaywgMSk7CiAgICBwcmludFNldCgnQicsbiwgMCk7CgogICAgYnQoKTsgICAgCgpyZXR1cm4oMCk7Cn07