• C

permutation code for flipping a coin

I am trying to write a program that produce all possible out come of flipping a coin "x" number of times, it has to be recursive and it produce an out come similar to this:
coin flipped 2 times
HTHHTHTT
I have some of the code done, but the output is a little confusing to what it should be.
thanks.
#include <stdio.h>
 
char coinflip(char* s, int size, int pos);
 
int main(void)
{
    char* s;
    int size;
    int pos;
    
printf("How many times will you be flipping a coin?\n");
scanf("%d", &size);
 
 
 
s=calloc(0, sizeof(char));
 
coinflip(s, size, 0);
printf("%s", s);
 
printf("Here are all your possible outcomes:\n");
 
 
 
system("pause");
return 0;
}
 
char coinflip(char* s, int size, int pos)
{
    if(size==pos)
    {
        return 0;
    //return coinflip(s, size, pos);
    }
    
    //posibility 1
    
    printf("H");
    return coinflip("H", size, pos+1);
    //posibility 2
    
    
    return coinflip("T", size, pos+1);
}

Open in new window

mikeregasAsked:
Who is Participating?
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Hi Mike,

What are you seeing?

Just a thought, but the coinflip function returns when size==pos.  I would think that that is the perfect place to call a function to print the result string.


Kent
0
 
Infinity08Connect With a Mentor Commented:
>> s=calloc(0, sizeof(char));

What's the point of allocating 0 bytes of memory ?


>>     return coinflip("H", size, pos+1);
>>     //posibility 2
>>     
>>     return coinflip("T", size, pos+1);

It seems like you want to do this recursively, right ? It'll be a bit more complicated than that ...
For one, you shouldn't return there, since the first return will invalidate the second.

Second, you probably want to append the results to the output string in some way.


What is the strategy that you want to follow to do this recursively ?

Why did you choose to do this recursively ? It doesn't seem like the best option to me, since this is an ideal problem to do iteratively.
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
>>  since this is an ideal problem to do iteratively

Actually, permutations lend themselves to recursive solutions very well.   :)  Of course, for a sequence of binary results (like a coin flip) there is a very good iterative shortcut, but I suspect that this is homework -- hence he doesn't have a lot of choice in the implementation.

Kent
0
Managing Security Policy in a Changing Environment

The enterprise network environment is evolving rapidly as companies extend their physical data centers to embrace cloud computing and software-defined networking. This new reality means that the challenge of managing the security policy is much more dynamic and complex.

 
Infinity08Connect With a Mentor Commented:
>> for a sequence of binary results (like a coin flip)

That's exactly what I was thinking of ;)
0
 
ozoConnect With a Mentor Commented:
> What's the point of allocating 0 bytes of memory ?
Maybe as a starting point for realloc
0
 
mikeregasAuthor Commented:
I need this do be done recursively, and I understand that you can not just give me the answer. I just need some clear direction on what it is I am trying to accomplish. I am lost with recursion and it confuses the hell out of me. I need to figure out how to search a binary tree that would have the results of the coin toss, if it is 2 tosses or 100 tosses and I need to get it to print to the screen the resullts of the binary 1 for heads and 0 for tails. 1=H and 0=T
0
 
Infinity08Connect With a Mentor Commented:
>> Maybe as a starting point for realloc

Except that the behavior of calloc is implementation defined when requesting allocation of a 0 size memory block. Generally it will return NULL, so you could have well set s to NULL instead. And if it returns a value different from NULL, you cannot use the memory it's pointing to.
So, I still don't see the point :)


>> I need to figure out how to search a binary tree that would have the results of the coin toss

I would suggest to draw an example tree (for a 3 coin toss for example) and see what it looks like. Figure out the best locations to show the results (where in the tree would you have access to all 3 tosses ?), and then implement the generation of that tree recursively.

This is pretty basic info, I know, but learning recursion is best done by figuring it out ... So, give it a try, and get back if you're stuck ...
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Hi Mike,

Recursion in this case should be fairly easy to understand, if you can walk through what, exactly, is happening.  And in this case, Infinity08's comment about this really being an iterative problem is a good place to start.

Let's think about a simple adder.  The Process takes the lowest (rightmost) ordered bits, adds them, and notes any carry bit.  It then moves left one bit, adds them and the carry bit, and notes any carry.  The process is repeated until all of the bits are added.

Here's a quick illustration of the results of a 2-bit (pardon the pun) adder.

  00   01   10   11
    1     1     1     1
  ==  ==   ==  ==
  01   10    11  00

In 4 passes, the adder has solved all possible combinations involving the incrementing of a 2-bit value.  In a sense, that is exactly what your recursive program is going to do.  Except that instead of iterating (looping) on each bit, the recursion will happen in such a way that each call of the flip() function handles all (both) of the states for its assigned bit.


To start with, allocate a buffer for *s* with 1 more character than you're trying to solve.  (If you want a 2-bit solution, allocate a 3 bit string.)

Now let's modify your flip() function just a bit.  The recursion logic will be exactly what you've built.  The only thing that needs help is what happens within the function.

We're going to build the output string so when we determine a value, we need to place it in the string.  Once the value is stored in the string, we'll recursively call the function again to process the next character.  When we have set a value for all of the characters, we'll print the string.

Take a look at the code below.  It's only a small change from what you have, and should work just fine with the rest of your program.


Good Luck,
Kent



char coinflip(char* s, int size, int pos)
{
    if(size==pos)
    {
        printf ("%s\n", s);
        return 0;
    }
    
    //posibility 1
    s[pos] = 'H';
    return coinflip (s, size, pos+1);
 
    //posibility 2
    s[pos] = 'T';    
    return coinflip (s, size, pos+1);
}

Open in new window

0
 
mikeregasAuthor Commented:
I understand what you are saying and I changed the flip function to what you suggested. However when I run the program and enter lets say 2 for flips it returns something way off like HH^2^2||||0F{... twice, why is that
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:

The last character of the string needs to be zero.  You called calloc() so I assumed that the buffer was already zero.

Just in case, the first test in the flip() function should look like this:

    if(size==pos)
    {
        s[pos] = 0;
        printf ("%s\n", s);
        return 0;
    }

I would expect the output to look like:

HH
HT
TH
TT


Kent
0
 
mikeregasAuthor Commented:
In the above example that you just gave me when the if returns 0; it goes to possibilty 1 and then possiblity 2 or does it just go to possibilty 1, because my out come is somewhat different than yours. it is:

HH
HH
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
My fault.

The embedded return statements shouldn't be there.  The entire function needs to run, unless pos > size.


Kent

void coinflip(char* s, int size, int pos)
{
    if(size==pos)
    {
        printf ("%s\n", s);
        return;
    }
    
    //posibility 1
    s[pos] = 'H';
    coinflip (s, size, pos+1);
 
    //posibility 2
    s[pos] = 'T';    
    coinflip (s, size, pos+1);
 
    return;
}

Open in new window

0
 
mikeregasAuthor Commented:
Kdo

I feel like I am bugging the hell out of you, but you are the only one that has really helped me understand this stuff.  The last thing is the last set of outcomes appears twice
ie.
HH
HT
TH
TT
TT
Got any ideas
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
You're not bugging me.  :)  (I have a wife, and a boss for that!)


Make sure that you don't print the array from the main program.  The function should handle the printing just fine.


Kent
0
 
mikeregasAuthor Commented:
lol I know exactly what you mean.  That was it, I entered 15 flips and the program stopped responding any ideas?
0
 
mikeregasAuthor Commented:
actually as soon as I got to 8 flips it ran through it, it just didnt get to the end of the program. It said the program stopped responding
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Understand that 15 flips is a lot of output.  :)  The number of results (also the number of lines of output) is 2^N so expect 2^15 (32K) lines.

Yeah.  :)

What parameters are you passing to calloc()?


Kent
0
 
mikeregasAuthor Commented:
That is alot of outputs. I am doing this for calloc():  s=calloc(0, sizeof(char));
should the sizeof be different ?
0
 
Infinity08Connect With a Mentor Commented:
>> I am doing this for calloc():  s=calloc(0, sizeof(char));

See my earlier comment about allocating a 0-size memory block. You shouldn't do that. Instead you should allocate enough space to put the result in ...
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
That's the problem....

calloc returns a buffer that is as large as you request.  You're asking for a buffer of 1 character.

The function is building a string that is 1 byte longer than *N*.  So you'll want to allocate a buffer at least N+1 bytes long.


Kent
0
 
mikeregasAuthor Commented:
so that would be  s=calloc(0, sizeof(char+1));
or am I ttotally off on this
0
 
Infinity08Connect With a Mentor Commented:
Take a look at the reference page for calloc :

        http://www.cplusplus.com/reference/clibrary/cstdlib/calloc.html

The second argument is the size of one element in bytes, and the first argument is the amount of elements you want to allocate memory for. The total amount of memory allocated will thus be the product of the two arguments. So, you're asking to allocate 0 * sizeof(char) = 0 bytes.
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Nope.

What is "char + 1"?   To C, it's jibberish.

The recursion can be only *N* calls deep.  Each recursive call (depth) sets T/H for the current character, puts it into the string, and calls the function again to handle the next character in the string.

So since we're building a string, we have to have a buffer large enough for the string.  That includes the final 0 byte (string terminator).

So if you're generating a string of 15 characters, you're going to need a 16 character buffer.  If you're generating a string of 7 characters, you're going to need an 8 character buffer.


Kent
0
 
mikeregasAuthor Commented:
so I want it to be 0 * sizeof(char) = 1 bytes and in order to do that I would have to do this
s= (char*) calloc (size,sizeof(char)); am I getting close here?
0
 
Infinity08Connect With a Mentor Commented:
>> s= (char*) calloc (size,sizeof(char));

Yes. Now, you just have to choose the right value for 'size'. Kdo already talked about that earlier ;)
0
 
mikeregasAuthor Commented:
I think that I am making this more difficult than it should be, but I would think that it would be size+1.
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Hi Mike,

Hint -- Immediately before you call calloc(), you get the value for size, which is the number of times the coin is to be flipped.

  :)

Obviously, you're struggling with this, so....

If you want a buffer of 100 characters, you can have the compiler generate them with the statement:

  char Buffer[100];

If you don't know how big the buffer needs to be so you plan to allocate it at run time, (just like you're doing here) you declare a pointer to the buffer and call calloc() or malloc() to assign memory to the buffer

  char *Buffer;

  Buffer = (char *) malloc (100);   // or Buffer = (char*) calloc (0, 100);

One of the things (niceties, to most of us) is that whether the array is defined as Buffer[100] or *Buffer, you can access any element of the array using normal array subscript syntax.

Buffer[2] is the third element (second after the first, indexing is relative 0) no matter how the array is declared.


Kent
0
 
Infinity08Connect With a Mentor Commented:
>> but I would think that it would be size+1.

If size is the amount of tosses you want to do, then that's right indeed :)
0
 
Infinity08Connect With a Mentor Commented:
>> // or Buffer = (char*) calloc (0, 100);

To avoid confusion, I assume that this was a typo in Kdo's post. It should be calloc(100, sizeof(char)) of course :)
0
 
mikeregasAuthor Commented:
so with size+1 the program should not crash?
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:

Not if that's the only issue.   :)


0
 
Infinity08Connect With a Mentor Commented:
>> so with size+1 the program should not crash?

It would not crash as long as the rest of your code is ok, and doesn't write outside of the boundaries of the allocated memory block.
0
 
Infinity08Connect With a Mentor Commented:
Maybe it's best to show your current code here, so we can have a look at it ...
0
 
mikeregasAuthor Commented:
sorry
s= (char*) calloc (size+1,sizeof(char));// this will keep it from crashing
s= (char*) calloc (size,sizeof(char));//or will this and I assume that the above would be the better choice when you get into the really high number of tosses correct. this one worked for 24 tosses it just takes a while to run through the program. I am testing the above one with 34 and as you can imagine it is still running
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:

The first one should do fine.


Kent
0
 
Infinity08Connect With a Mentor Commented:
I get the feeling you still don't fully understand how much memory you need to allocate, and especially why it needs to be done.

May I suggest to go over the posts in this thread again, and read them very carefully ? Kdo did a very good job explaining everything.

Next, it's a good idea to read up a bit about dynamic memory :

        http://www.cplusplus.com/doc/tutorial/dynamic.html

and C strings :

        http://www.cplusplus.com/doc/tutorial/ntcs.html
0
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
2^34 is 8 billion lines.

I hope that you're writing the output to disk and have a LOT of free space.  It will NEVER complete if you're writing it to the terminal.


Kent
0
 
mikeregasAuthor Commented:
thanks you guys were awesome and you both really helped me out alot, I really appreciate it.
Mike
0
 
Infinity08Commented:
>> I am testing the above one with 34 and as you can imagine it is still running

I don't think the point is to go that far ;) The point of an assignment like this is, is to come up with the algorithm and a proper implementation. The actual result is less important (as long as it's correct of course ;) ).

If it's working for sizes up to 5 (the ouput is still easy to verify in that case), then you're probably ok :)
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.