Thread: C program to find the number of onto functions and to display all of them

I have to write a C program (for my Discrete Mathematics assignment) that finds the number of onto functions from set A (|A| = m) to set B (|B|=n) and to display all those functions. I wrote the code for finding the number of onto functions.

But my problem is how to display all the functions?

If A = [1,2,3], B=[a,b,c] then the number of onto functions evaluated from the formula is
3^3 - 3(2^3) + 3 = 6.
One possible solution is f = [(1,a),(2,b),(3,c)]

But my problem is: How to display each and every solution!?

This is just a trivial example. But if m and n values are increased (provided m>=n) then the number of possible onto functions increases exponentially!!

I can't think of any method to display each and every function that exists between A and B.
So, I request the community to help me solve this problem.
Please help me!!!!
Thank you in advance.

I'm actually doing my 2nd year Bachelor of Engineering Course in Computer Science. Yes, I have taken an introductory course on C as well as Data Structures with C and yes, I have tried solving this problem.

However this question is actually a Mathematics question to be implemented in C. If you refer to my post you can know that.
I know that people don't do full home works here. I have tried displaying the functions using recursion. I have written an algorithm as well. But I'm not able to implement it in C.
That is why I asked help here.

Thank you

Displaying the number of functions is easy. I have already done it. The problem is displaying all of them. I need sample code to at least display the functions for the example I gave in the main post. I thought of using recursion. But I'm not able to implement the code in C.

If the number of functions is high, I need to display only some functions and say in a similar way there are ____ other functions.
Can u help me in displaying the functions for the sets I have given as example?

Originally Posted by vivek.1993

If A = [1,2,3], B=[a,b,c] then the number of onto functions evaluated from the formula is
3^3 - 3(2^3) + 3 = 6.

Are you sure? I would have thought the number is |B|! |B|^|A|-|B|, assuming |A| >= |B|, and |A| and |B| indicate the set sizes. How many functions are there if A = [1,2,3,4] and B=[a,b,c]? I count 18 (from f=[(1,a),(2,b),(3,c),(4,a)] to f=[(1,c),(2,b),(3,a),(4,c)]), but I may very well be mistaken.

Originally Posted by vivek.1993

But my problem is: How to display each and every solution!?

That is the wrong question. The correct question, and the path to a solution, is "How to display a specific solution?"

Think of all the solutions as an ordered set.

You need to write a function that takes the two lists A and B, and an integer specifiying the solution ([0, number of solutions -1], inclusive), and prints that one solution. Then you can have a loop that prints all, or perhaps just the first and last few solutions.

The way you create that function entirely depends on how you arrived at the formula for the number of solutions. If you think about it, that logic tells you exactly how to build any specific solution -- because the logic told you how the solution set could be ordered. If you just found a formula that fits, you're hosed: you'll need to understand how and why it works, to be able to solve this one.

Actually the number of solutions is given by

for(k=0; k<n; k++)
x = x + pow(-1,k) * comb(n,n-k) * pow(n-k,m);

The order of printing doesn't matter.

This is a kind of question where if you know the solution you can validate whether it is a function or not. It is quite difficult to 'display' the functions. The solution is derived by exclusion principle. That is we eliminate all other types of functions like one-one, constant etc. to get an onto function. No direct method as such.

A function is called Onto if every element in B has a pre-image in A.

it does seem like a very difficult combinatorial problem to generate the actual solutions. a brute force method, hinted at by vivek would be to generate every possible permutation of A to B and reject the ones that either are not valid onto. for example, start with f(a) and iterate over the elements of B so that f(a) = b[i]. for each of those cases then take f(b) and iterate over B etc. when you get to the last element of A in each case, then check the result to see if it is onto. it would hard to do with loops because you don't know the nesting levels ahead of time, so I expect a recursive solution of some sort would be easiest to code. but a way to start out would be to code against your initial test case using loops, and generate the cases and test them. this would give let you exercise your exclusion test and see if you ended up with the right number of answers. then think through how a recursive solution would be structured. now that i said loops would be hard, I expect to be proved wrong.

Using Loops this is really hard. Just consider all the functions from set A with m=3 to set B n=3. The total number of functions is 3^3 = 27. I require 3 for loops to display all the functions. The number of for loops depends on the number of elements in set B(correct me if I'm wrong). I am trying a recursive solution for this. I kind of figured out the logic too. But I'm not able to implement it into code(seems very difficult).

What I'm thinking is take set A as static(fixed) and B as dynamic. Rotate the dynamic array clockwise or counter-clockwise and print each element of B with each element of A.
Not able to proceed further... Need help.

Originally Posted by Nominal Animal

Are you sure? I would have thought the number is |B|! |B|^|A|-|B|

My combinatorics-fu is severely weak, it seems. There are of course

Code:

|B|! S(|A|, |B|)

functions, where S(m,n) are the Stirling numbers of the second kind (number of ways to partition m elements into n non-empty subsets).

Let's reset.

Since you are only interested in the N initial or final solutions, you can start with the set that contains |B|^|A| functions -- all solutions, plus those that do not map all elements in |B|.

Order this set of proposed solutions 0 .. |B|^|A|-1. This basically matches your outer loop. Not all iterations produce a result, so you'll most likely want to use a separate variable to hold the number of solutions provided.

Next, interpret the loop variable as a number in base |B|. That gives you |A| digits in base |B|. That is, if the loop variable is i, |A|=m, |B|=n, then the first proposed pair is (A[0], B[i mod n]), second is (A[1], B[(i / n) mod n]), and so on; in general (A[j], B[(i / n^j) mod n]).

A practical example, if A and B are specified as arrays of strings:

Code:

unsigned long print_solutions(FILE *const out,
                              const char *const A[], const unsigned long m,
                              const char *const B[], const unsigned long n)
{
    unsigned long  solutions = 0UL;
    unsigned long  proposed = 0UL;
    unsigned long  bref[m];
    unsigned char  used[n];
    unsigned long  curr, k;

    while (1) {

        /* Current proposed solution. */
        curr = proposed++;

        /* Clear the used element map. */
        memset(used, 0, sizeof used);

        /* Convert 'curr' to a radix n number. */
        for (k = 0; k < m; k++) {
            const unsigned long  digit = curr % n;

            /* Mark digit used. */
            used[digit] |= 1;

            /* Add index of digit to proposed solution. */
            bref[k] = digit;

            /* Next digit. */
            curr /= n;
        }

        /* If curr is nonzero, it was >= number of proposed solutions. */
        if (curr)
            break;

        /* Verify all elements in B were used. */
        for (k = 0; k < n; k++)
            if (!used[k])
                break;
        /* If not, this is not a true solution. */
        if (k < n)
            continue;

        /* This is a true solution. Print. */
        solutions++;

        printf("%lu. f([%s,%s]", solutions, A[0], B[bref[0]]);
        for (k = 1; k < m; k++)
            printf(", [%s,%s]", A[k], B[bref[k]]);
        printf(")\n");
    }

    return solutions;
}

Instead of printing all the solutions, you could print just a desired number of first and/or last solutions. (The if (curr) is only true if curr was >= m[sup]n , so you can also start at m[sup]n-1 and count downwards toward zero, if you want the final solutions instead.)

Unless I'm too drunk,

Code:

int main(void)
{
    static const char *const A[] = { "1", "2", "3", "4", "5" };
    static const char *const B[] = { "a", "b", "c" };
    unsigned long  n;

    n = print_solutions(stdout, A, sizeof A / sizeof A[0], B, sizeof B / sizeof B[0]);
    printf("%lu solutions total.\n", n);

    return 0;
}

does produce the expected 150 solutions, from f([1,c],[2,b],[3,a],[4,a],[5,a]) to f([1,a],[2,b],[3,c],[4,c],[5,c]).

This approach is still the same I originally described, except that you order a larger set that contains all the solutions, and some non-solutions too. Use a single integer to describe each unique solution -- that is what ordering means, after all. Usually you'll want to separate the integer to digits like above. Verify the solution is valid. Output the solution, and move to the next one.

Originally Posted by Nominal Animal

My combinatorics-fu is severely weak, it seems. There are of course

Code:

|B|! S(|A|, |B|)

functions, where S(m,n) are the Stirling numbers of the second kind (number of ways to partition m elements into n non-empty subsets).

Let's reset.

Since you are only interested in the N initial or final solutions, you can start with the set that contains |B|^|A| functions -- all solutions, plus those that do not map all elements in |B|.

Order this set of proposed solutions 0 .. |B|^|A|-1. This basically matches your outer loop. Not all iterations produce a result, so you'll most likely want to use a separate variable to hold the number of solutions provided.

Next, interpret the loop variable as a number in base |B|. That gives you |A| digits in base |B|. That is, if the loop variable is i, |A|=m, |B|=n, then the first proposed pair is (A[0], B[i mod n]), second is (A[1], B[(i / n) mod n]), and so on; in general (A[j], B[(i / n^j) mod n]).

A practical example, if A and B are specified as arrays of strings:

Code:

unsigned long print_solutions(FILE *const out,
                              const char *const A[], const unsigned long m,
                              const char *const B[], const unsigned long n)
{
    unsigned long  solutions = 0UL;
    unsigned long  proposed = 0UL;
    unsigned long  bref[m];
    unsigned char  used[n];
    unsigned long  curr, k;

    while (1) {

        /* Current proposed solution. */
        curr = proposed++;

        /* Clear the used element map. */
        memset(used, 0, sizeof used);

        /* Convert 'curr' to a radix n number. */
        for (k = 0; k < m; k++) {
            const unsigned long  digit = curr % n;

            /* Mark digit used. */
            used[digit] |= 1;

            /* Add index of digit to proposed solution. */
            bref[k] = digit;

            /* Next digit. */
            curr /= n;
        }

        /* If curr is nonzero, it was >= number of proposed solutions. */
        if (curr)
            break;

        /* Verify all elements in B were used. */
        for (k = 0; k < n; k++)
            if (!used[k])
                break;
        /* If not, this is not a true solution. */
        if (k < n)
            continue;

        /* This is a true solution. Print. */
        solutions++;

        printf("%lu. f([%s,%s]", solutions, A[0], B[bref[0]]);
        for (k = 1; k < m; k++)
            printf(", [%s,%s]", A[k], B[bref[k]]);
        printf(")\n");
    }

    return solutions;
}

Instead of printing all the solutions, you could print just a desired number of first and/or last solutions. (The if (curr) is only true if curr was >= m[sup]n , so you can also start at m[sup]n-1 and count downwards toward zero, if you want the final solutions instead.)

Unless I'm too drunk,

Code:

int main(void)
{
    static const char *const A[] = { "1", "2", "3", "4", "5" };
    static const char *const B[] = { "a", "b", "c" };
    unsigned long  n;

    n = print_solutions(stdout, A, sizeof A / sizeof A[0], B, sizeof B / sizeof B[0]);
    printf("%lu solutions total.\n", n);

    return 0;
}

does produce the expected 150 solutions, from f([1,c],[2,b],[3,a],[4,a],[5,a]) to f([1,a],[2,b],[3,c],[4,c],[5,c]).

This approach is still the same I originally described, except that you order a larger set that contains all the solutions, and some non-solutions too. Use a single integer to describe each unique solution -- that is what ordering means, after all. Usually you'll want to separate the integer to digits like above. Verify the solution is valid. Output the solution, and move to the next one.

Thank you very much for your answer. It was very helpful!

The solution works!! But, is it possible to make the code work more dynamically? Like I ask the user to input the values of m and n, and also the sets A and B and display the onto functions for those sets?