Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

permutation code for flipping a coin

Posted on 2008-10-06
39
Medium Priority
?
1,268 Views
Last Modified: 2008-10-06
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

0
Comment
Question by:mikeregas
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 13
  • 13
  • 12
  • +1
39 Comments
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 1040 total points
ID: 22650160
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22650192
>> 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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22650235
>>  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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22650362
>> for a sequence of binary results (like a coin flip)

That's exactly what I was thinking of ;)
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 80 total points
ID: 22650930
> What's the point of allocating 0 bytes of memory ?
Maybe as a starting point for realloc
0
 

Author Comment

by:mikeregas
ID: 22651168
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22652170
>> 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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22652442
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
 

Author Comment

by:mikeregas
ID: 22652603
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22652671

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
 

Author Comment

by:mikeregas
ID: 22652736
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22652978
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
 

Author Comment

by:mikeregas
ID: 22653108
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22653217
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
 

Author Comment

by:mikeregas
ID: 22653461
lol I know exactly what you mean.  That was it, I entered 15 flips and the program stopped responding any ideas?
0
 

Author Comment

by:mikeregas
ID: 22653593
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22653619
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
 

Author Comment

by:mikeregas
ID: 22653653
That is alot of outputs. I am doing this for calloc():  s=calloc(0, sizeof(char));
should the sizeof be different ?
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22653695
>> 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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22653698
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
 

Author Comment

by:mikeregas
ID: 22653755
so that would be  s=calloc(0, sizeof(char+1));
or am I ttotally off on this
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22653783
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22653806
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
 

Author Comment

by:mikeregas
ID: 22653943
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22653961
>> 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
 

Author Comment

by:mikeregas
ID: 22653994
I think that I am making this more difficult than it should be, but I would think that it would be size+1.
0
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22654030
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22654031
>> 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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22654038
>> // 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
 

Author Comment

by:mikeregas
ID: 22654053
so with size+1 the program should not crash?
0
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22654067

Not if that's the only issue.   :)


0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22654068
>> 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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22654073
Maybe it's best to show your current code here, so we can have a look at it ...
0
 

Author Comment

by:mikeregas
ID: 22654089
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22654104

The first one should do fine.


Kent
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 880 total points
ID: 22654112
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
 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 1040 total points
ID: 22654113
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
 

Author Comment

by:mikeregas
ID: 22654116
thanks you guys were awesome and you both really helped me out alot, I really appreciate it.
Mike
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22654160
>> 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

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question