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;
*/
}

---

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.

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);
}

---

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!

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.

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.

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.

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.

urg you are right, i knew my laziness would nip me in the butt evetually, will change compilers now

Quote:

---

Originally Posted by iMalc

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.

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.

Quote:

---

Originally Posted by quzah

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.

Quote:

---

Originally Posted by quzah

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!

Quote:

---

Originally Posted by iMalc

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

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.

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");
        }

}

---

There's another difference between returns and goto's.

Goto jumps to a specific point. Return jumps back to the instruction following the one
that called the function or subroutine. Return can return to various places, depending
on where it was called from.

If order matters then you're after permutations, not combinations.

Quote:

---

Originally Posted by quzah

The only difference is that returns can only jump backwards.

---

I strongly disagree here. You can't even use the word backwards really. I mean the function it returns to could be further on down in the file. But no, you can't call it forwards either. At best you can call it is a jump out. A goto can never do the job of a return as it can with a break or continue. In fact if you go back to the days of basic to a certain pont in history where there were no loop constructs at all, you had goto, gosub and return. Surprise surprise, return is actually the same as the old return.
Not only that, but where it was in this program (at the end) means that it does not affect control flow at all, and is in fact only used for the part of its job that has nothing to do with control flow at all and that's to provide the result to its caller. Calling the return in this program a goto, was a ridiculous stretch of the imagination by anyone's standards. And if that's a goto then there's one in every C program.

look liek teh formula I need to be using is: n!/(n-r)!

That look about right? Now to the coding!

Quote:

---

Originally Posted by iMalc

And if that's a goto then there's one in every C program.

---

That was my entire point. Every programmer that complains about gotos making code hard to read is simply glossing over the fact that they use things that do the exact same thing all the time.

As far as your disagreement to it being a jump backwards, that's fine. You're wrong, but it's fine for you to think that way. Consider the stack. Everything is on the stack (we're ignoring dynamic memory allocations, and are just talking about instructions). The stack is basically your C file flipped upside down.

So what does return do? It drops back down the stack to wherever your function call came from. What's that mean? It means you jumped backwards, tossing away everything above you, and overwriting the stack with new instructions. (Yeah yeah, you can shuffle things around and ruin my upside-down-source-code analogy if you really want to, but the concept holds true.)

So whenever you hit a return, you're jumping backwards to the point where the function was called. A label is in effect a function name, and a goto is in effect a return.


Quzah.

I don't program assembly on petiums, but I believe the stack only stores the return address
for the function. Not the executable code.

The calling code pushes the return address onto the stack, the address of the next instruction
following the JSR (jump to subroutine). The subroutine, or function pulls the return address
off the stack and then jumps (returns) there.

Quote:

---

Originally Posted by megafiddle

I don't program assembly on petiums, but I believe the stack only stores the return address
for the function. Not the executable code.

The calling code pushes the return address onto the stack, the address of the next instruction
following the JSR (jump to subroutine). The subroutine, or function pulls the return address
off the stack and then jumps (returns) there.

---

If you must know...

Code:

---

return address
parameter1
parameter2
etc.
local 1
local 2
etc.
push1
push2
etc.

---

... at the end of the function it merely resets sp to the address on entry and there's the return address. The rest of it is abandoned to be overwritten by the next function call. The return value is actually in a CPU register.

There are different protocals STDCALL, CDECL, FASTCALL etc... you can look these up for exact detail....

Yes, the stack stores more than just the return address.

I meant that the function itself is not stored on the stack. The function could conceivably
be anywhere in memory, and the calling code code also be anywhere. The "jump" that
is involved in the return is different from a goto (or JMP) statement. A JMP is to a specific
address or indirect address.

You could easily implement a 'for' or 'while' loop using goto's. Quite a bit different though
to implement a subroutine type return with a goto.

Quote:

---

Originally Posted by megafiddle

Quite a bit different though to implement a subroutine type return with a goto.

---

Well then I guess it's a good thing no one was comparing returning a value to a goto then, huh?

Quote:

---

Originally Posted by me

Conceptually they are identical, except for the part where return can also bring along a value with it.

---

Quzah.

Quote:

---

Originally Posted by megafiddle

Yes, the stack stores more than just the return address.

I meant that the function itself is not stored on the stack. The function could conceivably
be anywhere in memory, and the calling code code also be anywhere. The "jump" that
is involved in the return is different from a goto (or JMP) statement. A JMP is to a specific
address or indirect address.

You could easily implement a 'for' or 'while' loop using goto's. Quite a bit different though
to implement a subroutine type return with a goto.

---

Correct... the code is not on the stack... only the function's values end up there.

JMP and it's cousins... do not store a return address... CALL and it's cousins do...

Thus... subroutine != jump.

Quote:

---

Originally Posted by quzah

Well then I guess it's a good thing no one was comparing returning a value to a goto then, huh?
Quzah.

---

Actually... at the asm level, it is possible to load up a few registers then do a JMP instruction to code that operates on the values in the registers, just like a function call would. However; this functionality is not implemented in C ... (perhaps because it didn't exist back in the 70's when C was hatched...)

Quote:

---

Originally Posted by quzah

Well then I guess it's a good thing no one was comparing returning a value to a goto then, huh?
Quzah.

---

But what about functions that don't return anything?

How would you implement that with a goto instead of a return?

Quote:

---

Originally Posted by megafiddle

But what about functions that don't return anything?

How would you implement that with a goto instead of a return?

---

I wasn't trying to implement a function as a goto. But you could. Stick everything in main, then when you want to get where you're going, just stick a goto and get there.


Quzah.

Quote:

---

Originally Posted by quzah

I wasn't trying to implement a function as a goto. But you could. Stick everything in main, then when you want to get where you're going, just stick a goto and get there.
Quzah.

---

Right back to good old GWBasic... 1000 Goto 900.... :D

How do you get back, though, If you jumped there from different places?

edited: (double post) see next post

But then how do you get back? How do you know where that code was goto'ed from?

Code:

---

int camefrom;
...
handler:
switch( go )
{
    case 1: goto X;
    case 2: goto Y;
    ...
}
...
camefrom = something;
goto handler;

---

Off the top of my head? Something like that.


Quzah.

Quote:

---

Originally Posted by quzah

It's funny that everyone complains about goto, since most control statements are basically the same thing as goto.

---

I would say that abstraction is the key to understanding why control statements should be preferred to the use of goto, and in turn it explains where the use of goto is appropriate, i.e., where there is no suitable abstraction, as in the use of goto for error handling in the absence of say, exceptions.

Consider for example the use of std::for_each in C++ versus the use of std::copy to print a range: std::copy is "basically the same thing" as std::for_each, but the better abstraction provided by std::copy means that std::copy should be preferred.

Quote:

---

Originally Posted by quzah

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.

---

Yes, I consider continue to be a tool that should be used sparingly. That said, "does the same thing" accords too much credit to continue, since it cannot do what goto can do, i.e., jump to a point other than the start of the loop. This is a Good Thing because it is an abstraction for "jump to the start of the loop", which in turn makes reasoning about the flow of control easier (at the cost of having to learn yet another construct).

Quote:

---

Originally Posted by quzah

I wasn't trying to implement a function as a goto. But you could. Stick everything in main, then when you want to get where you're going, just stick a goto and get there.

---

And as long as the function is never called from two different places and is not recursive, then that's fine.

You focus only on ways X can be made to work like Y and ignore the ways in which Y cannot be made to work like X. If it quack's like a duck then it must be a duck. If you can shoot it out a cannon to make it fly then it surely must be a duck. In fact, if it floats then it must be a duck! You're certainly able to conclude that they are the same if the similarities are all you want to consider.

Well that was fun, we should do this again some time :wink:

Quote:

---

Originally Posted by iMalc

You focus only on ways X can be made to work like Y and ignore the ways in which Y cannot be made to work like X.

---

That's because I wasn't trying to prove they are identical. I was saying that they are similar. The reason people say to avoid goto is the same reason you shouldn't use continue: they both jump from one point in the code to another. It's silly to say not to use goto, and then follow up using a continue.

Quote:

---

Originally Posted by iMalc

Well that was fun, we should do this again some time :wink:

---

Indeed.


Quzah.

Quote:

---

Originally Posted by quzah

The reason people say to avoid goto is the same reason you shouldn't use continue: they both jump from one point in the code to another. It's silly to say not to use goto, and then follow up using a continue.

---

Not quite: as I observed in post #32, continue causes control to jump from the point of its use within a loop to the start of the loop. Small distinction, but it means that continue should be preferred to goto when you want control to jump from a point before the end of a loop back to the start of the loop. Consequently, it is not silly to advise against goto and then demonstrate continue. What might be lacking is that the change was only partial since the code could have been structured to do without the continue.

Quote:

---

Originally Posted by laserlight

Not quite: as I observed in post #32, continue causes control to jump from the point of its use within a loop to the start of the loop.

---

You mean like:

Code:

---

while/for
{

    if thing
        continue
    stuff...
}

---

Compared to:

Code:

---

while/for
{
    if thing
        goto cont;
    stuff...
    cont:
}

---

You can do the same thing with a goto.


Quzah.

Dr. Math can be helpful, perhaps:
Math Forum - Ask Dr. Math

Code:

---

For a final quick review of what I have presented above, here is my
thinking when I want to find the value of "9 choose 4":

C(9,4) = number of ways to choose 4 out of 9

        number of ways to choose 4 out of 9 if order is important
      = ---------------------------------------------------------
          number of different orders to choose each group of 4

        (four factors starting with 9 and decreasing by 1 each time)
      = ------------------------------------------------------------
        (four factors starting with 4 and decreasing by 1 each time)

          9*8*7*6
      = ---------
          4*3*2*1

And one more example, without all the words, just showing the numbers:

          10*9*8*7*6*5*4
C(10,7) = --------------
          7*6*5*4*3*2*1

---

Quote:

---

Originally Posted by quzah

You can do the same thing with a goto.

---

That is exceedingly obvious, and I am surprised that you did not bother to read my post #32 to understand why I made that statement, i.e., what was "small distinction" that I was talking about. Did you really think I was so ignorant as to assert that goto cannot do that? My assertion, if you had bothered to read, is that goto is more general purpose and thus can do more than just that, hence continue should be preferred as an abstraction when you just want to do that.

EDIT:
Furthermore, I stated that "continue should be preferred to goto (...)", so obviously, I did not dispute that goto could do that. You are blatantly setting up a strawman to attack.

Quote:

---

Originally Posted by laserlight

That is exceedingly obvious, and I am surprised that you did not bother to read my post #32 to understand why I made that statement, i.e., what was "small distinction" that I was talking about.

---

I did read it.

Quote:

---

Originally Posted by laserlight

Did you really think I was so ignorant as to assert that goto cannot do that? My assertion, if you had bothered to read, is that goto is more general purpose and thus can do more than just that, hence continue should be preferred as an abstraction when you just want to do that.

EDIT:
Furthermore, I stated that "continue should be preferred to goto (...)", so obviously, I did not dispute that goto could do that. You are blatantly setting up a strawman to attack.

---

There was no attack on anyone. I just observed, two pages back, that the the reasons people say to not use goto, is the same reason not to use continue. It breaks up the flow of your code, and jumps around from one spot to another. Then you all got it into your head that I was trying to prove one was superior or something. I don't know where that came from, but whatever.


Quzah.