Like Tree1Likes

All combinations

This is a discussion on All combinations within the C Programming forums, part of the General Programming Boards category; So I have been researching how to take n items, r at a time. Speed is important as right now ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    117

    All combinations

    So I have been researching how to take n items, r at a time. Speed is important as right now my processor is the bottle neck, not the hard drive (to my surprise).

    So right now my n is: H, B, C, N, P, O, S, Se, F, Cl, Br, I, F
    and i want to take it 5 at a time.

    I looked up the fastest way to do this an stumbled upon programming god Donald Knuth's algorithm of combinations in C, listed below.

    Problem is I can't figure it out and documentation I can understand is scarce. His "art of computer programming" book is way to technical for me.

    First off, it is a void main, so it doesn't even compile for me, even if i change it to int and return 0.

    Second, is the "visit:" etc actually code? I commented it out because I didn't think it is or never came across it.

    Thanks!


    Code:
    #include <stdio.h>
    #include <stdlib.h> 
    
    
    void main(void)
    {
    	int i, j=1, k, n, *c, x;
    	printf( "Enter n,k: ");
    	scanf( "%d,%d", &n, &k);
    	c = malloc( (k+3) * sizeof(int));
     
    	for (i=1; i <= k; i++)
    	{
    	c[i] = i;
    	c[k+1] = n+1;
    	c[k+2] = 0;
    	j = k;
    	}
    
    
    
    /*
    visit:
    	for (i=k; i >= 1; i--) printf( "%3d", c[i]);
    	printf( "\n");
    	if (j > 0) {x = j+1; goto incr;}
    	if (c[1] + 1 < c[2])
    	 {
    	 c[1] += 1;
    	 goto visit;
    	 }
    	j = 2;
    do_more:
    	c[j-1] = j-1;
    	x = c[j] + 1;
    	if (x == c[j+1]) {j++; goto do_more;}
    	if (j > k) exit(0);
    incr:
    	c[j] = x;
    	j--;
    	goto visit;
    */
    }

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    visit, do more and incr are just line labels.

    You need to include them! I'm not familiar with the code itself, but try using the whole thing.

    Check what your compiler needs for line labels though. I know in Turbo C, it required a semi-colon on the line immediately following the label:

    Code:
    visit:
    ;
    Your HD will be much more the bottleneck, AFTER you have filled up it's cache memory, not before.
    Last edited by Adak; 10-14-2011 at 02:55 PM.

  3. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    117
    well, I did include them all as is, but i get this error:
    Code:
    test.C:6: error: `main' must return `int'
    test.C: In function `int main(...)':
    test.C:10: error: invalid conversion from `void*' to `int*'
    test.C:44:2: warning: no newline at end of file

    If i change the main to int and return 0(code below) I get this error
    Code:
    test.C: In function `int main()':
    test.C:10: error: invalid conversion from `void*' to `int*'
    test.C:41:2: warning: no newline at end of file


    Changed main to int version:
    Code:
    #include <stdio.h>
    #include <stdlib.h> 
    
    
    int main()
    {
    	int i, j=1, k, n, *c, x;
    	printf( "Enter n,k: ");
    	scanf( "%d,%d", &n, &k);
    	c = malloc( (k+3) * sizeof(int));
     
    	for (i=1; i <= k; i++)
    	{
    		c[i] = i;
    		c[k+1] = n+1;
    		c[k+2] = 0;
    		j = k;
    	}
    
    visit:
    	for (i=k; i >= 1; i--) printf( "%3d", c[i]);
    	printf( "\n");
    	if (j > 0) {x = j+1; goto incr;}
    	if (c[1] + 1 < c[2])
    	{
    		c[1] += 1;
    		goto visit;
    	}
    
    	j = 2;
    
    do_more:
    	c[j-1] = j-1;
    	x = c[j] + 1;
    	if (x == c[j+1]) {j++; goto do_more;}
    	if (j > k) exit(0);
    
    incr:
    	c[j] = x;
    	j--;
    	goto visit;
    
    return(0);
    }
    Last edited by JonathanS; 10-14-2011 at 03:37 PM.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Remove the comma from inside the scanf() format string. Just enter the numbers as:

    number1 number2

    with no comma there, as you enter.

    I haven't run this program, but that code looks like it kicks some serious buttinski! Leave it to Knuth!
    Last edited by Adak; 10-14-2011 at 03:41 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    So you correct the code to int main and return 0 and then what? Uncomment everything, try to compile it and then post the errors you are getting.

    I doubt anybody cares what ridiculous lengths you have to go to to get Turbo Crap to work as we don't advocate using such obscenely out of date nonsense.

    Edit: Damn, crossed posts.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,495
    That error on line 10 is because you're compiling this as C++ code, which requires a cast from void * to any other type. C does not require a cast from void * to other pointer types, and in fact, casting malloc is not recommended in C code (read this: Cprogramming.com FAQ > Casting malloc).

    Also, that code you uncommented, while it may work, looks pretty crappy. It uses goto, which is generally considered bad practice (read: Goto Considered Harmful). Also, it uses a bunch of variable names that make no sense and it's totally uncommented, so it's hard to say what it really does.

    If you want combinations where order doesn't matter and there are no repeats, and you always want combinations of 5 elements, then you can hack it with a bunch of nested for loops:
    Code:
    #define N_ELEMENTS    13
    char *elements[N_ELEMENTS] = {"H", "B", "C", "N", "P", "O", "S", "Se", "F", "Cl", "Br", "I", "F"};
    int a, b, c, d, e;
    
    for (a = 0; a < N_ELEMENTS - 5; a++) {
        for (b = a + 1; b < N_ELEMENTS - 4; b++) {
            ...
                    for (e = d + 1; e < N_ELEMENTS; e++) {
                        printf("%s %s %s %s %s\n", elements[a], elements[b], ..., elements[e]);
                    }
        }
    }
    Note, that's untested, but should give you the general idea.
    Last edited by anduril462; 10-14-2011 at 03:41 PM. Reason: too many irons in the fire

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Oh, GOOD catch, Anduril!

    void main() was an option in Turbo C, but was NOT standard in it.

    To my eyes, this looks like a very fast utility bit of a program. You treat it as a black box, and just use it once it's checked, whenever. No further comments needed, and no problem with the goto's either. It's just intuitive to Knuth, and written back in the day when goto's were common, I would guess.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Here is the code with basically a direct translation to remove the gotos:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    {
        int i, j=1, k, n, *c, x;
        printf("Enter n,k: ");
        scanf("%d,%d", &n, &k);
        c = malloc((k+3) * sizeof(int));
    
        for (i=1; i <= k; i++)
        {
            c[i] = i;
            c[k+1] = n+1;
            c[k+2] = 0;
            j = k;
        }
    
        for (;; j--)
        {
            for (i=k; i >= 1; i--)
                printf("%3d", c[i]);
            printf("\n");
    
            if (j > 0)
                x = j+1;
            else
            {
                if (c[1] + 1 < c[2])
                {
                    c[1] += 1;
                    continue;
                }
    
                for (j=2; ; j++)
                {
                    c[j-1] = j-1;
                    x = c[j] + 1;
                    if (x != c[j+1])
                        break;
                }
                if (j > k)
                    break;
            }
    
            c[j] = x;
        }
    
        return 0;
    }
    Removing them is not really that hard, and certainly improves the readability of the flow of the code. Although as you can see the code is still very strange looking anyway.
    Last edited by iMalc; 10-14-2011 at 04:13 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2011
    Posts
    117
    urg you are right, i knew my laziness would nip me in the butt evetually, will change compilers now

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by iMalc View Post
    Here is the code with basically a direct translation to remove the gotos:
    Code:
    ...
                    c[1] += 1;
                    continue; /* basically a goto */
                }
                /* could be an else block instead of that continue */
                /* which is also basically a goto... */
                for (j=2; ; j++)
                {
                    c[j-1] = j-1;
                    x = c[j] + 1;
                    if (x != c[j+1])
                        break; /* pretty much a goto */
    ...
        return 0; /* also basically a goto :P */
    }
    It's funny that everyone complains about goto, since most control statements are basically the same thing as goto.


    Quzah.
    itCbitC likes this.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,495
    I guess everything basically has a goto:
    Code:
    a = 1;  // pretty much a goto next instruction
    b = a * 2 + 5;  // pretty much another goto next instruction
    A strange game. The only winning move is not to play.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by quzah View Post
    It's funny that everyone complains about goto, since most control statements are basically the same thing as goto.


    Quzah.
    Yep! good point as they get translated into branch or jump statements, viz. the assembler's version of gotos.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by quzah View Post
    It's funny that everyone complains about goto, since most control statements are basically the same thing as goto.
    Fine, conveniently ignore all the things that break, else, and continue can't do that goto can, and instead focus on the one thing that they can all do. Surely, all the most convincing scientific studies also conveniently throw away half of the data.

    Okay so I missed an opportunity to use an else instead of a continue. One point is that I made it possible to see such an opportunity.

    But really... a return is "also basically a goto". Dream on!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by iMalc View Post
    Fine, conveniently ignore all the things that break, else, and continue can't do that goto can, and instead focus on the one thing that they can all do. Surely, all the most convincing scientific studies also conveniently throw away half of the data.
    It wasn't sniping at you, I was pointing out that a continue is just a goto. All you are doing is jumping from where you are, to another point. People always say goto is bad because it makes the code hard to follow. Well, a continue does the same thing. It short circuits the flow of the loop and jumps back to the start.
    Quote Originally Posted by iMalc View Post
    But really... a return is "also basically a goto". Dream on!
    Of course it is. You are jumping from the middle of one function back to another. Conceptually they are identical, except for the part where return can also bring along a value with it.

    The concept of jumping around from one point to another is what I was drawing parallels with. A goto and a return leap from wherever you are, to another spot in the code. The only difference is that returns can only jump backwards.


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Registered User
    Join Date
    Sep 2011
    Posts
    117
    Some very juicy tid bits here! I have finally changed to a C compiler, which solved the problems. Thanks to all!

    I'll be using anduril462's way because it is easier to understand.

    There is only one problem, both ways of output order does not matter. I need one that doesmatter (because of enantiomers). I am going to tinker with the code to see if I could make it do it, but if there is already a person who made this it would be appreciated for them to post it for me to save time :P

    Code for anyone interested:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define N_ELEMENTS 13
    /*
    PROBLEM for later = Order does not matter, need to make it so it does
    */
    
    
        char *elements[N_ELEMENTS] = {"H", "B", "C", "N", "P", "O", "S", "Se", "F", "Cl", "Br", "I", "F"};
        int a, b, c, d, e;
    
        void write_File(char** elements, int a, int b, int c, int d, int e);
    
    
    int main()
    {
    
    
        for (a = 0; a < N_ELEMENTS - 5; a++)
        {
            for (b = a + 1; b < N_ELEMENTS - 4; b++)
            {
                for (c = b + 1; c < N_ELEMENTS - 4; c++)
                {
                    for (d = c + 1; d < N_ELEMENTS - 4; d++)
                    {
                        for (e = d + 1; e < N_ELEMENTS; e++)
                        {
                            printf("%s %s %s %s %s\n", elements[a], elements[b], elements[c], elements[d], elements[e]);
                            write_File(elements, a, b, c, d, e);
                        }
                    }
                }
            }
    
        }
    
        return(0);
    }
    
    
    void write_File(char** elements, int a, int b, int c, int d, int e)
    {
    
    	FILE* fts;
    
    	fts = fopen("data.dat", "a");
    
    	if (fts)
    	{
    		fprintf(fts, "%s %s %s %s %s\n" , elements[a],  elements[b], elements[c], elements[d], elements[e]);
    		fclose(fts);
    	}
    
    
    	else
    	{
    		printf("Error writing to file!\n");
    	}
    
    }

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with combinations !!!!
    By ayan_2587 in forum C Programming
    Replies: 2
    Last Post: 12-12-2009, 11:45 AM
  2. Combinations
    By Cmuppet in forum C Programming
    Replies: 6
    Last Post: 10-19-2004, 07:39 AM
  3. Combinations, lotto, 6/49
    By Robert in forum C++ Programming
    Replies: 8
    Last Post: 12-06-2002, 06:27 PM
  4. key press combinations
    By Trauts in forum C++ Programming
    Replies: 2
    Last Post: 10-01-2002, 12:15 PM
  5. Combinations
    By GaPe in forum C Programming
    Replies: 16
    Last Post: 01-09-2002, 04:38 AM

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