|
Here's one method I just thought of:
Plinko algorithm:
<code>
Private function SelRand(target as integer, _
lbound as integer, ubound as integer) as integer
dim n as integer
dim i as integer
dim x as integer
dim loops as integer
n = target
if abs(n-ubound) > abs(n-lbound) then
loops = abs(n-ubound)
else
loops = abs(n-lbound)
end if
for i = 0 to loops
x = int(rnd * 3)
Select Case x
Case 0: if n > lbound then n = n - 1
Case 1: if n < ubound then n = n + 1
case 2: ' drop down to same number
End Select
Next i
SelRand = n
End Function
</code>
So basically by the law of averages the target number and its neighbors will be hit more often, but there's still a possibility of all numbers being selected.
Can you think of any optimizations to this method? Any other ways to do this?
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
-- modified at 12:39 Thursday 30th August, 2007
|
|
|
|
|
I implemented this plinko algorithm and it works fine for what I need it to do. Thanks for your help, guys.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Hi,
if you want an integer number j in the range [min, max) where each possible
value j has a different probability, you could:
- define an array P[j] that holds the relative probability (we use integers,
i.e. the absolute probability multiplied by N, the sum of all P[j])
- use a random number generator to obtain a number k in the range [0, N)
- find the value of j for which SUM(P(j)<=k<sum(p(j+1))
where="" sum="" is="" taken="" over="" [min,="" j).
btw:="" the="" notation="" [a,b)="" means="" range="" from="" a="" up="" to="" b,="" including="" a,="" excluding="" b.
the="" final="" transformation="" k--="">j can be speeded up by:
- storing SUM(P(j)) for all j
- and even, if N is not too large, using an array of size N
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Neat idea Luc, to phrase it in a slightly different way, take the interval (0,1) and split it into N subintervals defined by {0, x1, x2, .., xN-2, 1}, the length of each nth subinterval is the assigned probability to the nth event. Then use a uniform RV in the interval (0,1) and choose event n if the RV lands in the nth subinterval. You can easily find the subinterval in O(log2(N)).
Of course this only works for discrete events, but reading between the lines this is probably what the OP wanted.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
that's what engineers like to do: linearize the world as much as possible.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
cp9876 wrote: only works for discrete events
Not so sure, the words would change, it would become an integral rather than a
sum, and the optimizations would have to be revisited of course, but the basic
idea could still work.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
I only have a very vague idea of what you're talking about, not being an engineer or mathmetician myself, but from what I gather, you're suggesting a similar idea to the one I was thinking of on my own: building a pyramid of probabilities from the peak target down to all values at the base, and then selecting values based on that.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
The differences between the ideas presented is the probability distribution function that results - this means the probability of each number occurring. If you have 100 numbers, the pdf is simply the probability of each occurring p1, p2 ,..p100. These must sum to 1.
My post suggested generating them with a normal distribution (bell curve), so if you were to plot the p's you would see a bell-shaped curve. The other suggestion, generating two uniform RVs in the range 1..50 and adding them would give a triangular shape if you plotted the p's.
The clever thing about Luc's post is that he can arbitrarily specify the pdf. He can do the triangular one, or have 3 peaks, two valleys and a plateau! Just by specifying the probabilities the same algorithm will generate the numbers.
I suspect that your algorithm would also give a triangular shaped plot, but with clustering around the endpoint that you were closer to (due to the way you stay in range), and dropping away around the more distant endpoint. You could easily run a large number of samples and plot the histogram to see.
Depending on the application the pdf may be very important or not. If you are generating random numbers to simulate the noise in a communications system for example, the large ones cause the errors and it is important that these are generated at the right rate relative to the others.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hi,
I need to generate random points inside of rectangle. But I need to have a certain distance between neighboring points. My input is rectangle and interval of distances <d1, d2="">. When I have a point P1, distance between P1 and any of closest points must be from <d1, d2="">. Is there any effective algorithm to do that?
noIdea
|
|
|
|
|
I don't understand your question. Are you saying that you need to generate random points located on a rectangular grid? If so, the co-ordinates are simply (nx*dx, ny*dy) where dx,dy are the grid spacings and nx and ny are integers. Simply generate random integers nx and ny.
Alternatively, if the points can be randomly located, but each extra one must be >d from each other, then I can't think of a better way than generating them randomly and rejecting each new one if it is too close to the existing ones. You could speed up the searching by storing the generated points in some sort of grid pattern.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I also don't quite understand what you are looking for, but if you are looking for a "uniform" distribution function you can use the boost libraries: http://www.boost.org/libs/random/random-distributions.html[^]
if that is not what you are looking for, google on "random number distribution function" and see if the one you want pops up.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
noIdea77 wrote: When I have a point P1, distance between P1 and any of closest points must be from
where from? the interval of distances ? is that a list of minimal distances alowed between points? can you use just a single distance? how many points ? (clearly if there is a minimal distance, you can have only so many points)
the question sounds interesting, but I, for one, does not understand its terms completely.
there are no facts, only interpretations
|
|
|
|
|
Simple way:
Assuming
r = random number from 0 to 1
Xmin and Xmax = limit value of X
Ymin and Ymax = limit value of Y
Then
generate X = Xmin + r * (Xmax - Xmin) [and Y = Ymin + r * (Ymax - Ymin) ]
test if the distance from (X,Y) to the last valid (X,Y) generated is great than a the desired value, if not generate another point (X,Y)
Complex way:
Use the polar coordinates (it will become a not uniform distribution)
Start point is the last valid point (X,Y) found, now you need to generate the new point as a direction and a distance to move it.
First generate a random angle uniformely from 0 to 360 degrees.
Then generate a random distance uniformely from a minimal to a maximal distance: the minimal distance is the desired minimal distance from 2 consecutive points. The max distance is the simple calculation of the border of the rectangle moving with the found angle.
(when the maximal apceptable distance is less then the minimal distance then this means that this angle is not valid, the rectangle border is too near,...so the solution is simply to generate another random angle value)
Russell
|
|
|
|
|
3d table cells. Easy. Mid grey for the cell. Light grey - top / left borders. Dark grey - bottom / right borders. Easy. Greys are easy in RGB though - keep R G B the same , ie EE EE EE - very light grey. 11 11 11 - very dark grey.
Now - I want a 3d blue cell, or a 3d orange cell, or a 3d slightly purple cell. I know the colour of the cell, but what formula can I apply to 'lighten' this colour for the highlight, and darken for the shadow....
On your marks....get set....[reply from Luc / CPallini....damn - that was quick]
"More functions should disregard input values and just return 12. It would make life easier." - comment posted on WTF
"I haven't spoken to my wife now for 48 hours. I don't like to interrupt her.
|
|
|
|
|
|
Sorry, I am having an off day.
What can I add to ingc's reply? In Java the Color class has methods that return
a lighter/darker shade of a given color, unfortunately .NET does not offer this.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: unfortunately .NET does not offer this
In .NET the Color class doesnt do that, but there is a class ControlPaint (in System.Windows.Forms) that offers the static methods Dark(), DarkDark(), Light(), LightLight()
|
|
|
|
|
I just discovered this myself.
I am not sure the results are good enough, seems like they took the easy way out
(without much HSL conversion); DarkDark as far as I can see is always Black ?
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: I am not sure the results are good enough
You are right about the quality. But you can be lazy (ControlPaint) or good (do it your own way).
|
|
|
|
|
Researchers in England may have finally settled the centuries-old debate over who gets credit for the creation of calculus.
For years, English scientist Isaac Newton and German philosopher Gottfried Leibniz both claimed credit for inventing the mathematical system sometime around the end of the seventeenth century.
Now, a team from the universities of Manchester and Exeter says it knows where the true credit lies — and it's with someone else completely.
Article[^].
|
|
|
|
|
Hi,
this may interest me, unfortunately Internet Explorer 6.0 crashes on the link. 
Firefox survives it tho.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: this may interest me, unfortunately Internet Explorer 6.0 crashes on the link.
Hmmm, it was fine for me and I was using IE...
|
|
|
|
|
All they say in that article is that they discovered an infinite series without saying what it was. I don't really see what infinite series has to do with calculus. I think I'd need a more more information than that before I could judge wether they had really discovered calculus. The positive integers from 1 to infinity are an infinite series and I wouldn't rate them highly for discovering that.
|
|
|
|
|
A Noteworthy Programmer wrote: I don't really see what infinite series has to do with calculus.
Just about everything, actually...
|
|
|
|
|
Infinite series are used for way more that just calculus. Calculus is involved with the study of what happens when you let the step sizes used in area calculations and gradient calculations and such like become infinitlely small.
An infinite series is genereally any equation who's terms go forever, which could be like the series 1/2+1/4+1/8+... etc...
Anyway my main point is that they didn't really say what those Indian mathematicians had discovered which is what I was really interested in knowing on reading that article. Maybe this news item is on some other web site with more information?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
