Like Tree1Likes

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

This is a discussion on C program to find the number of onto functions and to display all of them within the C Programming forums, part of the General Programming Boards category; I have to write a C program (for my Discrete Mathematics assignment) that finds the number of onto functions from ...

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    9

    Exclamation 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.

  2. #2
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,483
    There is a homework policy found here - Announcements - General Programming Boards

    With that in mind, what have you come up with so far? Have you done an intro to C coarse?
    Fact - Beethoven wrote his first symphony in C

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,883
    Hmm... if you are only supposed to find the number, then why do you need to display all the functions? But if you need to display all the functions, then you have to display all the functions, even if there are a very large number of them such that you won't be done displaying them by next Christmas. In such a case, your instructor will presumably choose input that will result in a suitably small number of functions to be displayed.

    On the other hand, if you're saying that you are permitted to abbreviate the display of all the functions by using mathematical notation, then you might as well just throw the formula back at the user and state that that displays all the functions, once expanded.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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.

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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?

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,483
    Sure

    You said that you have done an algorithm and a bit of code already - Note that we will not do your work for you. If you supply your solution, we will help you develop your own solution.

    I'd advise you to look into the sscanf function, an array of chars and a 'for' loop.
    Fact - Beethoven wrote his first symphony in C

  8. #8
    Registered User
    Join Date
    Oct 2011
    Posts
    851
    Quote Originally Posted by vivek.1993 View Post
    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.

    Quote Originally Posted by vivek.1993 View Post
    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.

  9. #9
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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.

  10. #10
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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.

  11. #11
    Registered User
    Join Date
    Mar 2011
    Posts
    546
    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.

  12. #12
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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.

  13. #13
    Registered User
    Join Date
    Oct 2011
    Posts
    851
    Quote Originally Posted by Nominal Animal View Post
    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 / nj) 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.
    vivek.1993 likes this.

  14. #14
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    Quote Originally Posted by Nominal Animal View Post
    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 / nj) 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!

  15. #15
    Registered User
    Join Date
    Nov 2012
    Posts
    9
    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?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 13
    Last Post: 05-02-2012, 04:17 PM
  2. Replies: 4
    Last Post: 03-17-2012, 01:37 AM
  3. Write a program to find the factors of any number entered.
    By rajesh10071986 in forum C Programming
    Replies: 5
    Last Post: 01-20-2010, 02:15 PM
  4. number display
    By paulogrady in forum C++ Programming
    Replies: 2
    Last Post: 10-11-2008, 04:15 AM
  5. Display a number in a MessageBox
    By Coding in forum C++ Programming
    Replies: 2
    Last Post: 01-26-2008, 12:34 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21