#include <stdio.h>
#define SIZE 100
int stack[ SIZE ],
level,
n,
m;
int init() {
stack[level] = 0;
};
void print() {
int i;
for(i
= 1; i
<= n
; i
++) printf("%d ",i
); printf("\n---------------\n"); for(i
= 1; i
<= n
; i
++) printf("%d ", stack
[i
]);
};
int succ() {
if(stack[level] < m) {
stack[level]++;
return 1;
}
return 0;
};
int surjective() {
int i,j,flag;
for(i = 1; i <= m; i++) {
for(j = 1, flag = 0; j <= n && !flag; j++) {
if(stack[j] == i) flag = 1;
}
if(!flag) return 0;
}
return 1;
};
int valid() {
if(level == n) {
if(!surjective()) return 0;
}
return 1;
};
int sol() {
return level == n;
};
void bt() {
int hs, is;
level = 1;
init();
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(int n){
int it;
for(it = 1; it <= n; it++) {
}
};
int main() {
// freopen("Generating.All.Surjective.Functions.out", "w",stdout);
printf("%s\n","Generating All The Surjective Functions:\n");
//f : A -> B
//A = {1,2,3}, B = {1,2} {(1,1,2),{1,2,1},(1,2,2),{2,1,1},(2,1,2)}
printSet(n);
printf("CoDomain -> card(B) "); printSet(m);
bt();
return(0);
};
I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgU0laRSAxMDAKCmludCBzdGFja1sgU0laRSBdLAogICAgbGV2ZWwsCiAgICBuLAogICAgbTsKCmludCBpbml0KCkgewoKICAgIHN0YWNrW2xldmVsXSA9IDA7Cn07Cgp2b2lkIHByaW50KCkgewoKICAgICBpbnQgaTsKCiAgICAgcHJpbnRmKCJ4ICAgICAgfCAiKTsKICAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKSBwcmludGYoIiVkICIsaSk7CiAgICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLVxuIik7CiAgICAgcHJpbnRmKCJmKHgpICAgfCAiKTsKICAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKSBwcmludGYoIiVkICIsIHN0YWNrW2ldKTsKCiAgICAgcHJpbnRmKCJcblxuIik7Cn07CgppbnQgc3VjYygpIHsKCiAgIGlmKHN0YWNrW2xldmVsXSA8IG0pIHsKCiAgICAgIHN0YWNrW2xldmVsXSsrOwoKICAgICAgcmV0dXJuIDE7IAogICB9CiAgIHJldHVybiAwOwp9OwoKaW50IHN1cmplY3RpdmUoKSB7CgogICAgaW50IGksaixmbGFnOwoKICAgIGZvcihpID0gMTsgaSA8PSBtOyBpKyspIHsKCiAgICAgICAgZm9yKGogPSAxLCBmbGFnID0gMDsgaiA8PSBuICYmICFmbGFnOyBqKyspIHsKCiAgICAgICAgICAgICAgICBpZihzdGFja1tqXSA9PSBpKSBmbGFnID0gMTsKICAgICAgICB9ICAKCiAgICAgICAgaWYoIWZsYWcpIHJldHVybiAwOyAgICAgICAgIAogICAgfSAgCiAgICByZXR1cm4gMTsgCn07CgppbnQgdmFsaWQoKSB7CgogICAgaWYobGV2ZWwgPT0gbikgewoKICAgICAgIGlmKCFzdXJqZWN0aXZlKCkpIHJldHVybiAwOwogICAgfSAKCiAgICByZXR1cm4gMTsgCn07CgppbnQgc29sKCkgewoKICAgIHJldHVybiBsZXZlbCA9PSBuOwp9OwoKdm9pZCBidCgpIHsKCiAgICAgaW50IGhzLCBpczsKCiAgICAgbGV2ZWwgPSAxOwoKICAgICBpbml0KCk7CgogICAgIHdoaWxlKGxldmVsID4gMCkgewoKICAgICAgICAgICBocyA9IDE7IGlzID0gMDsKCiAgICAgICAgICAgd2hpbGUoaHMgJiYgIWlzKSB7CgogICAgICAgICAgICAgICAgIGhzID0gc3VjYygpOwoKICAgICAgICAgICAgICAgICBpZihocykgaXMgPSB2YWxpZCgpOwogICAgICAgICAgIH0KCiAgICAgICAgICAgaWYoaHMpIHsKCiAgICAgICAgICAgICBpZihzb2woKSkgcHJpbnQoKTsKCiAgICAgICAgICAgICAgICBlbHNlIHtsZXZlbCsrO2luaXQoKTt9CgogICAgICAgICAgIH0gZWxzZSBsZXZlbC0tOyAKICAgICB9ICAKfTsKCnZvaWQgcHJpbnRTZXQoaW50IG4pewoKICAgICBpbnQgaXQ7CiAgICAgcHJpbnRmKCJcbnsiKTsKICAgICBmb3IoaXQgPSAxOyBpdCA8PSBuOyBpdCsrKSB7CiAgICAgICAgIHByaW50ZigiJWQgIixpdCk7CiAgICAgfQogICAgIHByaW50ZigifVxuIik7Cn07CgppbnQgbWFpbigpIHsKICAgIAogLy8gICBmcmVvcGVuKCJHZW5lcmF0aW5nLkFsbC5TdXJqZWN0aXZlLkZ1bmN0aW9ucy5vdXQiLCAidyIsc3Rkb3V0KTsKIAogICAgcHJpbnRmKCIlc1xuIiwiR2VuZXJhdGluZyBBbGwgVGhlIFN1cmplY3RpdmUgRnVuY3Rpb25zOlxuIik7CiAgICAKICAgIC8vZiA6IEEgLT4gQgogICAgLy9BID0gezEsMiwzfSwgQiA9IHsxLDJ9IHsoMSwxLDIpLHsxLDIsMX0sKDEsMiwyKSx7MiwxLDF9LCgyLDEsMil9CgogICAgcHJpbnRmKCJEb21haW4gLT4gY2FyZChBKSAiKTsKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgcHJpbnRTZXQobik7CiAgICBwcmludGYoIkNvRG9tYWluIC0+IGNhcmQoQikgIik7CiAgICBzY2FuZigiJWQiLCZtKTsKICAgIHByaW50U2V0KG0pOwogICAgcHJpbnRmKCJcbiIpOwogICAgYnQoKTsgICAgCgpyZXR1cm4oMCk7Cn07