Probability Q - Page 2

[Moschops]

Whup. Answered (and coded) the wrong question after all. I stand corrected. 1+39. Cheers, Nezachem.

These are two completely different questions.

Pffft. They're hardly completely different. :)

[histrungalot]

way down below

First match?

[pjh-10]

moschops is the code u gave here, on page 1, is it fully correct, just wondering?
made a wee start to this today, will give an update later hopefully!

[pjh-10]

#include <iostream>
#include <cstdlib>   
#include <ctime>
#include <cmath>
using namespace std;

int main() {
    int song[1000];    
    int n;           
    srand(time(0));  

    for (int i=0; i<1000; i++) {
        song[i] = i;  
    }

    while (cin >> n) {    

        for (int i=0; i<(1000-1); i++) {
            int r = i + (rand() % (1000-i)); 
            int temp = song[i]; song[i] = song[r]; song[r] = temp;
        }


        for (int c=0; c<n; c++) {
            cout << song[c] << " ";  
        }
        cout << endl;
    }

   return 0;
}

riteo, this is the random number generator, its works fine, luckily. so im only an absolute beginner, feel free to pick out any faults or mistkaes there, also where would be the next place to go , ie the next step.
thanks

[pheininger]

#include <iostream>
#include <cstdlib>   
#include <ctime>
#include <cmath>
using namespace std;

int main() {
    int song[1000];    
    int n;           
    srand(time(0));  
     
    for (int i=0; i<1000; i++) {
        song[i] = i;  
    }
    
    while (cin >> n) {    
        
        for (int i=0; i<(1000-1); i++) {
            int r = i + (rand() % (1000-i)); 
            int temp = song[i]; song[i] = song[r]; song[r] = temp;
        }
        
        
        for (int c=0; c<n; c++) {
            cout << song[c] << " ";  
        }
        cout << endl;
    }
   
   return 0;
}

riteo, this is the random number generator, its works fine, luckily. so im only an absolute beginner, feel free to pick out any faults or mistkaes there, also where would be the next place to go , ie the next step.
thanks

1) So it appears that you want to simulate the original situation given in your assignment. Assuming that this is for a class, it is not clear if the instructor wants you to simulate the issue or write a program to do the direct calculation. You may want to confirm which (or possibly either) is allowed by your instructor. Some of the people who have responded in this thread have taken each of these points of view.

2) If I am reading your code correctly, this will take 1000 songs numbered 0 to 999 and put them in a randomized order similar to shuffling a deck. However, also similar to shuffling a deck, there is no possibility for a repeat. So your shuffled list of songs cannot possibly include a repeat. This does not sound like what the original assignment was giving as the situation.

3) Are you taking a programming class or are you taking a probability class? If you are in a programming class, have you had a probability or statistics class? If not, you may want to study (or have the instructor explain) the probability involved before you try to do any more coding.

4) To summarize, I am concerned that you are solving the wrong problem with the code. So it may not matter if the code works as you intend it. It is difficult (if not impossible) to write correct code until one knows what are the requirements.

[pjh-10]

you want to find out how many songs play before a previous played song comes up again, thats the task. the answer is less than 50 songs, that much i know. so want to do the shuffle, and feed the random number you get back into a loop, which breaks when that previous song comes up, ie. being less than 50!

[pheininger]

you want to find out how many songs play before a previous played song comes up again, thats the task. the answer is less than 50 songs, that much i know. so want to do the shuffle, and feed the random number you get back into a loop, which breaks when that previous song comes up, ie. being less than 50!

Hint: So you do not need to do a shuffle at all.

The next song is a uniform distribution of song number 0 to 999. It does not matter what the previous song is for selecting the next song. Do you know how to do this calculation? You were close to embedded the right calculation in your shuffle code. If I wanted to make this a function, I would give it the declaration

int SelectNextSong(void);

It is small enough that I might not make it a function, but it some times good to do these things in steps. Do you see how to write that function?

If you are going to solve this by a simulation, for each sequence of played songs, you do need to keep track of the songs that have already played. If you newly selected song is one of the ones already played, this particular simulation is completed. I might declare this function

int LengthNonRepeatSequence(void);

For both of these functions you may want to pass the number of songs as a parameter or just make it a global constant.

Then you need to do a large number of these sequence simulations so that you can get the average length of the sequences until a repeat (by simulation) (if that is what you are supposed to do).

Or it is also likely that you have been assigned to find out when the probability that the length of a non-repeating sequence is less than 50%. In which case, the direct calculation for that was given to you 11 days ago in the first page of responses.

The difference between these two calculations was the discussion in the middle of the thread. And it is very easy to get "fooled" between these two because the difference in valuse is about 1. Both of them are less than 50.

[pjh-10]

how do you get the random number generated, fed into a loop(so that it repeats until, the fed number is repeated) so the loop then breaks. im a pure beginner, i know that no-one is gonna just copy & paste an answer, but a basic explanation would be so good, or any useful weblinks.

[pheininger]

how do you get the random number generated,
- using rand() function
fed into a loop
- use the loop to generate the songs in sequence
- keeping a record of the songs played in an array or vector
(so that it repeats until, the fed number is repeated)
- look back through the played songs using another nested loop
so the loop then breaks.
- if a matching song is found (using an if statement)
- break out of the loops using a break instruction, boolean flag, return statement, or goto

[Lerner]

Here's another "experimental" approach, in pseuocode:

declare an array of type bool, size 1000---say boolArray.
declare an int called numSelectiions
1) set boolArray to all false
2) set numSelections to 0
3) pick a random number, i, between 0 and 999
4) increment numSelections by one
5) if boolArray is true, stop
6) else assign true to boolArray
7) repeat lines 3-6 if needed.
8) calculate aveNumberOfSelectionsNeededBeforeARepeat after each trial
9) Repeat 1-7 until you're happy

[pjh-10]

having a bit of trouble for the array part, il let u's know in a bit, will update soon!

[pjh-10]

#include <iostream>
#include <cstdlib>   
#include <ctime>
#include <cmath>
using namespace std;

int main ()
{
    int x,y,shuffle, song;

    song = (1+(rand()%(1000-(x-1))));
    srand (time(NULL));

        for (x=0;x<1000;x++)
        { 
            shuffle = (1+(rand()%(1000-(x-1))));

                if(shuffle == song)
                {
                    break;
                }
        }

    cout<< x << endl;

return 0;
}

[Lerner]

Here's a pencil and paper example of my previous suggestion using a scaled down version of the process to get your hands and head around the concepts without feeling overwhelmed. See if it makes sense to you. If so change it to pseudo code and then to code.

bool arr[3] = false

TRIAL 1:
first pick  is 1;
arr[1] is false 
  assign true to arr[1] 

second pick is 0
arr[0] is false
  assign true to arr[0]
 
third pick is 1
arr[1] is true
  stop this trial since we have picked this number before

this trial took 3 picks to repeat value 
ave picks to repeat is 3

reset arr to all false

TRIAL 2:
first pick is 2
arr[2] is false
  assign true to arr[2]

second pick is 2
  arr[2] is true 
  stop this trial since we've picked this number before

This trial took 2 picks to repeat value
Ave picks to repeat is (3 + 2)/2 = 2.5

reset arr to all false

TRIAL 3:
first pick is 0
arr[0] is false
 assign true to arr[0]
 
second pick is 1
arr[1] is false
 assign true to arr[1]
 
third pick is 2
arr[2] is false
 assign true to arr[2]

fourth pick is 1
arr[1] is true
 stop this trial as we've picked this value before

This trial took 4 picks to repeat value
Ave picks to repeat is (3 + 2 + 4)/3 = 3

Expand this to an array of 1000 booleans
Repeat as many time as you want to get an answer for the average number of times it takes to get a repeat you feel comfortable with.

[pheininger]

Here is your latest code inside code tags. Please use them in the future.

#include <iostream>
#include <cstdlib>   
#include <ctime>
#include <cmath>
using namespace std;

int main ()
{
	int x,y,shuffle, song;
	
	song = (1+(rand()%(1000-(x-1))));
	srand (time(NULL));

		for (x=0;x<1000;x++)
		{ 
			shuffle = (1+(rand()%(1000-(x-1))));

				if(shuffle == song)
				{
					break;
				}
		}
		
	cout<< x << endl;
	
return 0;
}

1) What is the value of x at line 11?
2) What is the purpose of the "-(x-1)" in lines 11 and 16? For each song selected, are not all values from 1 to 1000 equally likely?
3) For debugging reasons alone, either use your debugger or output to the console to see what the values of the songs selected are?
4) You listed code but what questions or issues do you have with it?

[pjh-10]

1) What is the value of x at line 11?
2) What is the purpose of the "-(x-1)" in lines 11 and 16? For each song selected, are not all values from 1 to 1000 equally likely?
3) For debugging reasons alone, either use your debugger or output to the console to see what the values of the songs selected are?
4) You listed code but what questions or issues do you have with it?

1-2// not really sure, im seen this on various sites, for random number generation
3// we weren't really taught or ever told to use the debugger
4// just showing an update of my work so far!

[raptr_dflo]

Since it's been a day or so, I'll jump in!

The "x-1" you've seen is part of the process of shuffling an array, which isn't part of this assignment. The reason it exists, if you look back to your earlier code sample which shuffled the song list, is because by the time you get to the last song in the list, there's nothing left to shuffle it with.

Picking a random song is as simple as rand()%1000 (which gives you values in the range [0,999] with approximately equal probability).

Your code so far checks only whether any future song matches the first song. This is incorrect, and has already been discussed endlessly in this thread. Each time you pick a new song, you need to check whether it matches -any- of the previously selected songs. The good news is, none of the previous songs will match another previous song, or you would have quit the loop already.

I will reiterate, because it's important in general - programming anything is an exercise in precise thinking. If you can't think through the problem you're trying to solve, the program you're writing won't solve it (except maybe by accident). You need to be able to think through the process of solving the problem, in steps small enough that they correspond to lines of code. The "top down" approach breaks the solution of the problem from a single item ("the solution") into a few high level steps ("first do A", "then do B", "finally do C"), and then breaks each of those steps into sub-steps, and so on. Once you've gotten your thinking about the problem and its solution sufficiently precise, the program pretty much writes itself.

And while a debugger is convenient, it is often sufficient to insert a line like:

cout << "the current value of x is " << x << endl;

wherever in your code it's useful to see what's going on. You can always remove them later. :)

[pheininger]

1) What is the value of x at line 11?
1-2// not really sure,

For the first question, your "answer" is absolutely correct! x is an automatic int variable. Automatic variables have scope from the time they are defined or declared until the end of the block in which they are declared. You did not initialize it so it can have any value (typically referred to a garbage). Then in line 11, it is being used without having been set.

If you have the warnings setting set appropriately with your compiler, you may get warnings for cases like this.

2) What is the purpose of the "-(x-1)" in lines 11 and 16? For each song selected, are not all values from 1 to 1000 equally likely?

1-2// not really sure, im seen this on various sites, for random number generation

The expression rand() % <max_rand> where <max_rand> is an integer expression is a resonable way to get an approximately uniformly distributed psuedo-random number in the range from 0 ... <max_rand>-1. The % is the modulus operator; it will give the remainder from an integer division. In your case, <max_rand> would be 1000 which will get numbers in the range of songs from 0 to 999. If you want, you could add 1 to the expression to get a range from 1 to 1000, but I bet that eventually complicates your work. There are minor problems with this expression so that is why "approximately", but for student work it is good enough.

Remember you need to seed the random number generator by using the srand() function once and only once near the beginning of your program (typically early in main()). Very commonly this is done using srand(time(NULL));. Look both these functions up to know what header files you need to include and to make sure I am not remembering something wrong.

3) For debugging reasons alone, either use your debugger or output to the console to see what the values of the songs selected are?

3// we weren't really taught or ever told to use the debugger

You do not have to use a debugger. Just add additional output statements as shown in the prior messsage so that you can see what is going on with values of important expressions. I had suggested it because your random expression (if I read it correctly) was not going to get you a distrbution from 1 to 1000 but from 1 to 1001-x.

I hope you make good progress.

[pjh-10]

ah im not making much headway atm, 12 days or so to do it, unfortunately!

[pjh-10]

making a brand new start, ive too many other attemps,lol. starting from scratch,icluding libraries!! =]

[pjh-10]

#include <iostream>
#include <cstdlib>   
#include <ctime>
#include <cmath>
using namespace std;

int main() {
    int song[1000];    
    int n;           
    srand(time(0));  
     
    for (int i=0; i<1000; i++) {
        song[i] = i;  
    }
    
    while (cin >> n) {    
        
        for (int i=0; i<(1000-1); i++) {
            int r = i + (rand() % (1000-i)); 
            int temp = song[i]; song[i] = song[r]; song[r] = temp;
        }
        
        
        for (int c=0; c<n; c++) {
            cout << song[c] << " ";  
        }
        cout << endl;
    }
   
   return 0;
}

can anyone one says whats wrong here, is it cause of an infinite loop,as theres no output on the compiler? thanks

[raptr_dflo]

No, it's not an infinite loop. You're not getting any output because your program is waiting for your input, at line 16 above.

And why are you back to creating a shuffled list of songs?

[raptr_dflo]

I'm going to recommend a different approach here. You're programming blindly by incorporating code you've written (or been given) previously, that addresses a different problem. You're very clearly not learning anything that way. So here's what I recommend. Throw out all your code AGAIN, now. And start over, but not yet.

Instead, grab some paper and a pen or pencil (remember those?), and write down what your program needs to do. Not the problem you've been given, that's already written, but what steps need to be provided in the solution, in order to answer the question. If it helps, pretend you're the music player. What do you do? Divide that answer up into individual steps. Then divide those steps into more steps. Respond here with your steps. If you respond with code, I'll come to your house and beat you up. Just kidding about that last part, but don't go back to programming until you're clear about what you're going to program.

(Extra credit: As far as shuffling the list of songs ahead of time, what does that do for you? What does it guarantee? Why is that a good idea? Why is it not appropriate for this assignment?)

[pjh-10]

if i was an ipod all i want is to shuffle the songs, and then again shuffle them, and then go through songs as in (next) depending on where a previously played song comes up.
regarding loop,i think this is how you do it: using shuffle get a song ( just an int value) store that value,as an array. shuffle again, then next through each song, saving each song thats has played until you get to the previously played one, doing this until you have a good average of times.
that it?

[raptr_dflo]

I went back and looked at your first posting, and it does indeed say "with shuffle", which I had neglected. If that is an accurate copy of the original problem-statement, then I think you're on the right track.

Your shuffle-based solution has a particularly nice behavior: repeats are spread very far apart. You are guaranteed to be able to play at least N songs before playing a song you've played before. What is that value of N? (It should be obvious, it has nothing to do with running your program to determine the average value of N.)

Given your approach outlined above, I don't know what average value I'd expect, maybe ~1038?

Allow me to re-state your algorithm above, does it match what you think you're doing?

// pseudocode!
shuffle songs
save this order into another list  // these are the songs you'll play through the first time with no repeats
shuffle songs again
determine the first time you get a repeat and save how many songs were between that song and its previous occurrence, and save that value

If I have that correct, you can optimize your efficiency a great deal. After you've shuffled the songs the second time, isn't the first song in the re-shuffled list guaranteed to have been played at some point in the run-through of the first-shuffled list? If that's the case, you don't need to reshuffle all the songs for the second list -- since you just need the first song in the list (the order of the other 999 songs is irrelevant), you can just pick a single random song to be that first song in the re-shuffled list. Right?

Finally, how do you do the "keep doing this until you have a good average of times" part? It will probably help to have a couple of functions you can re-use, to make your code more readable and understandable. I recommend the following:

void shuffleSongs(int songs[], int num_songs)
{
    // implement shuffling here
    // note: it probably doesn't matter if you start with the songs in order, and then shuffle them,
    // or if you just keep re-shuffling the songs (after the first time)
}

int chooseRandomSong(int start, int end)
{
    // pick a random song between start and end-1 (*), and return it
    // note: this could possibly be used by shuffleSongs()
    //(*) or include end, whichever you prefer, just make sure you code this function correctly, and call it correctly.
}

int testNumberOfSongsBetweenRepeats(int num_songs)
{
    // run the algorithm we're working out:
    // determine for the first repeated song, how many songs were between the two occurrences, and return that value
}

float runTestManyTimesAndComputeAverage(int num_songs, int num_runs)
{
    // create a loop where you call the above function the specifed number of times,
    // and compute and return the average value
}

// and of course you'll have a main() which calls runTestManyTimesAndComputeAverage() and prints out the result.

[pheininger]

well got sort of a briefing into this, and the answer is less than 50 songs! i need 2 prove this just!

To the pjh-10:

I think you have become too hung up on the word "shuffle". I believe that in the music player world, there are two features available. One where the next song is selected at random and another where the user can have the songs "shuffled" so that they get a different order but all songs in the playlist are just played a single time. The second one seems to be the "shuffling" that you are trying to write code for.

You indicated some place early in the thread (and I have quoted above) that the answer is less than 50. This indicates to me that what your instructor wants is for you to use the uniformly selected random number for the next song and NOT to "shuffle" the song list.

(Extra credit: As far as shuffling the list of songs ahead of time, what does that do for you? What does it guarantee? Why is that a good idea? Why is it not appropriate for this assignment?)

Here raptr_dflo has asked you all the correct questions if I am right about the next song being uniformly randomly selected. But I would like to put it another way.

I first learned the word "shuffle" with regards to playing cards such as are used to play poker, bridge, or gin rummy. Before one shuffles the deck, there is only one card of each rank and suit combination. When one shuffles playing cards or simulates that in a computer, the deck still has only one of each card. So if one deals, there can be no repeated cards. I bet you found software which you copied that tries to implement this kind of shuffle.

I went back and looked at your first posting, and it does indeed say "with shuffle", which I had neglected. If that is an accurate copy of the original problem-statement, then I think you're on the right track.

Your shuffle-based solution has a particularly nice behavior: repeats are spread very far apart. You are guaranteed to be able to play at least N songs before playing a song you've played before. What is that value of N? (It should be obvious, it has nothing to do with running your program to determine the average value of N.)

Given your approach outlined above, I don't know what average value I'd expect, maybe ~1038?

Allow me to re-state your algorithm above, does it match what you think you're doing?

// pseudocode!
shuffle songs
save this order into another list  // these are the songs you'll play through the first time with no repeats
shuffle songs again
determine the first time you get a repeat and save how many songs were between that song and its previous occurrence, and save that value

So raptr_dflo has given advice based on if the instructor really meant "shuffle" the songs every X number of song selections. But as I said, I do not think this is what your instructor wanted. I do not think you need to "shuffle" anything. You just need to select the next song played uniformly from the 1000 songs.

However, no matter which model is used, raptr_dflo has given you a function structure to proceed. This is superset of the functions that I suggested one or two pages back (at least in how I view this thread).

In my opinion, you could proceed with this project using either bottom up approach or mostly top down approach. For either approach, you test and debug each step until you have a working program. For many of these steps, the next step uses the function that you wrote in the prior step or if it was not a function, restructures the code to make it a function. For the most part, where I have suggested function names I have used those suggested by raptr_dflo; feel free to select your own. I am using single character names for some of the values in this description; use more descriptive names in your program.

Bottom up:

• Write a program that selects a uniformly randomly selected ("ums") song from S possible songs and displays it.
• Write a program that selects (using ums) (using chooseRandomSong() for what you did above) and displays up to P played songs from S possible songs.
• Write a program that selects P played songs from S possible songs and remembers the songs played (in probably an array or vector) and then displays the songs played from that memory.
• Write a program that selects songs from S possible songs remembering the songs played until there is a repeat and displays either the number of songs played without a repeat (possible results from 1 to S) or the song selection number when there was a repeat (possible results from 2 to S+1). These are obviously one different from each other.
• Write a program repeats the step above for T trials. For this program, what is described in the step above becomes testNumberOfSongsBetweenRepeats()
• [Optional step] Write a program that accumulates the number of song non-repeats from T trials.
• Write a program that average the results of the T trials given above. Optionally consider making this the function runTestManyTimesAndComputeAverage(). Display the result.

Mixed Approach:

• Take your working "Hello world" program and change it so it prints an average (also known as a double) returned from a function. You could name that function runTestManyTimesAndComputeAverage().
• Write a program that averages the results from T calls to a function OneTry() that returns an integer (which in our case is the number of songs played without a repeat). Display the average (and for debugging purposes possibly the integers returned). For now, just have OneTry() return 42 so the average displayed will be 42.0. This means that you are incorrectly simulating the next layer down, but that is OK until you get this part right.
• Write a program that averages the results from T calls to OneTry(). Have OneTry() return the randomly selected song played from S songs. For a large number of trials T, this should return an average of S/2.
• Change the above program so that the function OneTry() is named chooseRandomSong(). Write a new OneTry() that just calls chooseRandomSong(). For a large number of trials T, this should return an average of S/2.
• Write a program that displays the average from T calls to OneTry() where OneTry() random selects P plays from S songs where . For simulation, OneTry() returns that last song played. Again the average should be S/2.
• Write a program that displays the average from T calls to OneTry(). This time OneTry() random selects P plays from S randomly selected songs and saves the songs played in an array or vector. You may want to display the remembered songs played for debug purposes, but you will want to remove this for the next round. When you are displaying the remembered songs, you will want to keep the T trials and P plays small or you will be overwhelmed with output. For simulation, OneTry() still returns that last song played. Again the average should be S/2.
• Write a program that displays the average from T calls to testNumberOfSongsBetweenRepeats() where testNumberOfSongsBetweenRepeats() is your OneTry() from the previous program. But this time, for each song played, look back through the remembered songs and stop playing songs when either there is a repeat or P plays have happened. If there is a repeat, return the current play-1 or P if there have not been any repeats. I cannot predict what average will be returned.
• Change the above program so that the number possible plays P is the same as the number of songs S.

[pjh-10]

As ive said, my c++ is terrible, barely above beginning, so a lot of the above is way over my head tbh! but i have to say, i appreciate the selfless help you's all are giving me,regardless of my struggling, il go through the above more thoroughly later hopefully.
from the last code i posted, where would i go from there? thanks

[pheininger]

from the last code i posted, where would i go from there? thanks

From my point of view, either 1) if you are going to keep to a "shuffle" design that is not required, fix the while expression (I think (my C++ is limited also) the value of (cin >> n) is cin not whatever you were thinking) or 2) remove the "shuffle" which gets rid of the while.

[Lerner]

The song names are irrelevant to the algohrythm so simplify your life and use an array of 1000 boolean variables.

bool songs[1000]
char ch;
int totalSelections = 0
int numTrials = 0
int x
bool anotherTrial = true
while(anotherTrial) 
  //set variables for this trial to default values
  for(i = 0; i < 1000; ++i)
    songs[i] = false
  ++numTrials
  numSelections = 0
  noRepeat = true

  //run this trial
  while(noRepeat)
    randomShuffle(songs)
    randomly assign a value to x between 0 and 999
    ++numSelections

    //if this selection was picked before
    if(songs[x]) 
      totalSelections += numSelections
      averageSelectionsTilRepeat = totalSelections/numTrials
      noRepeat = false
    else  //this selection wasn't picked before, but has been now, so make it true
      songs[x] = true
  
  enter n if you want to stop further trials
  cin >> ch
  if(ch == 'n')
    anotherTrial = false

[raptr_dflo]

As ive said, my c++ is terrible, barely above beginning, so a lot of the above is way over my head tbh! but i have to say, i appreciate the selfless help you's all are giving me,regardless of my struggling, il go through the above more thoroughly later hopefully.
from the last code i posted, where would i go from there? thanks

No worries, that's why we're here.

As far as where to go from here, and being "terrible" at C++, do the work recommended by pheininger above. It will start improving your C++, and get you all the way to your solution. Nothing stated should be "over your head". Instead of being overwhelmed by how big it looks, just start at the first "Write a program ..." bullet. Just do that much, specifically: "Write a program that selects a uniformly randomly selected ("ums") song from S possible songs and displays it." It's less than 10 lines of code. Don't worry about what the next bullet says until you have the previous one done.

And as I said previously in this thread, and in others as well, programming is ALL about precise thinking. When the whole problem is too big to think about (and it will always be that way -- as you get better at programming, the problems you try to tackle will get harder), just break off bite-sized chunks and deal with those, and then put the pieces together when you're ready.

Good luck, and we'll still be here for you if/when you get stuck. But really, do the work, that's how you'll improve. (In case you were wondering, stressing out over an assignment doesn't improve your programming abilities. Well, it didn't for me, anyway. :) )

[pjh-10]

well im irish and its a big weekednd for me, so the programmings gonna have to take a wee break until monday are so!