Solved

permutation code for flipping a coin

Posted on 2008-10-06
39
1,227 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
  • 13
  • 13
  • 12
  • +1
39 Comments
 
LVL 45

Accepted Solution

by:
Kdo earned 260 total points
Comment Utility
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 220 total points
Comment Utility
>> 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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
>>  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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 220 total points
Comment Utility
>> 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 20 total points
Comment Utility
> What's the point of allocating 0 bytes of memory ?
Maybe as a starting point for realloc
0
 

Author Comment

by:mikeregas
Comment Utility
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 220 total points
Comment Utility
>> 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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility

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
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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 220 total points
Comment Utility
>> 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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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 220 total points
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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 220 total points
Comment Utility
>> 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
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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 220 total points
Comment Utility
>> 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 220 total points
Comment Utility
>> // 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
Comment Utility
so with size+1 the program should not crash?
0
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility

Not if that's the only issue.   :)


0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 220 total points
Comment Utility
>> 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 220 total points
Comment Utility
Maybe it's best to show your current code here, so we can have a look at it ...
0
 

Author Comment

by:mikeregas
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility

The first one should do fine.


Kent
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 220 total points
Comment Utility
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 45

Assisted Solution

by:Kdo
Kdo earned 260 total points
Comment Utility
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
Comment Utility
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
Comment Utility
>> 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

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
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 how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

728 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now