fork download
copy 
  1. #include <stdio.h>
  2. #define SIZE 100
  3.  
  4. int stack[ SIZE ],
  5.     level,
  6.     n,
  7.     m;
  8.  
  9. int init() {
  10.  
  11.     stack[level] = 0;
  12. };
  13.  
  14. void print() {
  15.  
  16.      int i;
  17.  
  18.      printf("x      | ");
  19.      for(i = 1; i <= n; i++) printf("%d ",i);
  20.      printf("\n---------------\n");
  21.      printf("f(x)   | ");
  22.      for(i = 1; i <= n; i++) printf("%d ", stack[i]);
  23.  
  24.      printf("\n\n");
  25. };
  26.  
  27. int succ() {
  28.  
  29.    if(stack[level] < m) {
  30.  
  31.       stack[level]++;
  32.  
  33.       return 1; 
  34.    }
  35.    return 0;
  36. };
  37.  
  38. int surjective() {
  39.  
  40.     int i,j,flag;
  41.  
  42.     for(i = 1; i <= m; i++) {
  43.  
  44.         for(j = 1, flag = 0; j <= n && !flag; j++) {
  45.  
  46.                 if(stack[j] == i) flag = 1;
  47.         }  
  48.  
  49.         if(!flag) return 0;         
  50.     }  
  51.     return 1; 
  52. };
  53.  
  54. int valid() {
  55.  
  56.     if(level == n) {
  57.  
  58.        if(!surjective()) return 0;
  59.     } 
  60.  
  61.     return 1; 
  62. };
  63.  
  64. int sol() {
  65.  
  66.     return level == n;
  67. };
  68.  
  69. void bt() {
  70.  
  71.      int hs, is;
  72.  
  73.      level = 1;
  74.  
  75.      init();
  76.  
  77.      while(level > 0) {
  78.  
  79.            hs = 1; is = 0;
  80.  
  81.            while(hs && !is) {
  82.  
  83.                  hs = succ();
  84.  
  85.                  if(hs) is = valid();
  86.            }
  87.  
  88.            if(hs) {
  89.  
  90.              if(sol()) print();
  91.  
  92.                 else {level++;init();}
  93.  
  94.            } else level--; 
  95.      }  
  96. };
  97.  
  98. void printSet(int n){
  99.  
  100.      int it;
  101.      printf("\n{");
  102.      for(it = 1; it <= n; it++) {
  103.          printf("%d ",it);
  104.      }
  105.      printf("}\n");
  106. };
  107.  
  108. int main() {
  109.  
  110.  //   freopen("Generating.All.Surjective.Functions.out", "w",stdout);
  111.  
  112.     printf("%s\n","Generating All The Surjective Functions:\n");
  113.  
  114.     //f : A -> B
  115.     //A = {1,2,3}, B = {1,2} {(1,1,2),{1,2,1},(1,2,2),{2,1,1},(2,1,2)}
  116.  
  117.     printf("Domain -> card(A) ");
  118.     scanf("%d",&n);
  119.     printSet(n);
  120.     printf("CoDomain -> card(B) ");
  121.     scanf("%d",&m);
  122.     printSet(m);
  123.     printf("\n");
  124.     bt();    
  125.  
  126. return(0);
  127. };
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
3 2
stdout
copy 
Generating All The Surjective Functions:

Domain -> card(A) 
{1 2 3 }
CoDomain -> card(B) 
{1 2 }

x      | 1 2 3 
---------------
f(x)   | 1 1 2 

x      | 1 2 3 
---------------
f(x)   | 1 2 1 

x      | 1 2 3 
---------------
f(x)   | 1 2 2 

x      | 1 2 3 
---------------
f(x)   | 2 1 1 

x      | 1 2 3 
---------------
f(x)   | 2 1 2 

x      | 1 2 3 
---------------
f(x)   | 2 2 1
https://ideone.com/s8qT61
Generating Surjective Functions.
language:
C (gcc 8.3)
created:
47 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!