|
Munchies_Matt wrote: Undeveloped babies. THat is a difficult topic!
No worse than eating chicken's eggs? 
|
|
|
|
|
Did you know you can't run through a campsite? You can only ran, because it's past tents.
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
As forest I can tell, it's lucky you didn't stake your reputation on that post.
| Ravings en masse^ |
|---|
| "The difference between genius and stupidity is that genius has its limits." - Albert Einstein | | "If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010 |
|
|
|
|
|
Ran Forrest, ran!
... such stuff as dreams are made on
|
|
|
|
|
But who will play the direct object than?
In Word you can only store 2 bytes. That is why I use Writer.
|
|
|
|
|
Can't wait til tomorrow, so we can have s'more of these puns.
"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
"I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle
|
|
|
|
|
huh? what is your in tent? it's way past reason.
Installing Signature...
Do not switch off your computer.
|
|
|
|
|
the best time to make love is when camping.
It's in tents.
veni bibi saltavi
|
|
|
|
|
Fishing can be good too if you bring Annette.
i can see Carly now Lorraine is gone...
|
|
|
|
|
|
My gawd! Time travel!
Have I really been doing this for over two years? 
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Does that mean he has to change is name to un-OriginalGriff?
Hogan
|
|
|
|
|
What if the tents were a gift from a Bernie Sanders supporter? Wouldn't that make them present progressive tents?
An if they were given to a dedicated outdoorsman, wouldn't that make them present perfect tents?
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
Apparently this is a popular shuffling algorithm. Unfortunately it has a couple of problems with it.
First, OrderBy is not a linear time operation, while shuffling should be. That is already sufficient reason to stop using it to shuffle, especially on big lists, but there is more.
Less obviously, it does not choose a permutation with uniform probability across all possible permutations. This will be clear if we intentionally make it worse first and work from there. Consider
list.OrderBy(x => random.Next() & 1)
Now every element only gets a random bit. Assume we shuffle a list with 2 elements A and B, there are only 2 outcomes, AB and BA. BA happens when the first element gets a 1 and the second element gets a 0. AB happens in all other cases, because in the case of a draw they are left in their original order.
This is obviously bad. One outcome is chosen with probability 0.25, and the other with probability 0.75. With more random bits both probabilities get closer and closer to 0.5, but they never quite make it all the way there.
Larger lists are worse. The probability of two elements being assigned the same random number gets large enough to worry about really quickly, which you have heard about as the birthday paradox. Any time a group of elements is assigned the same random number, those elements will not be reordered. Of course it is OK to not reorder elements, but the probability of that happening is larger than it should be. This is especially noticeable for lists larger than the space from which random numbers are drawn.
Consider what would have happened if the snippet above was used to sort a list of 3 elements, A B and C. At least 2 of them must get the same random value, because there are only two different values to randomly draw. That means that at least 2 elements remain in their original order, so it is impossible to generate CBA. For the full number of random bits this problem only happens for lists with over 2 billion elements, but for shorter lists it is still the case that permutations with many inversions are generated with a probability that is too low.
Here's an other way to look at it. Clearly it would work if all elements were assigned a unique random number. That is equivalent to applying a permutation with a key-value sort, which is a common (though inefficient) technique. It doesn't even need to be a permutation on the numbers 0 to N-1, it's OK if there are "gaps", that's just a relabeling. So as long as only unique random numbers are generated, it's fine. What is the probability that that does not happen? If I got the formula right then that means that for a list of length 10000 there is already a probability of 2% that you're in a "bad case" (with some duplicate), quickly growing to 90% for size 100000. In practice that would still be really hard to notice since those "bad cases" don't create an immediate problem, they're just subtly skewing the probability distribution, but it is still wrong.
|
|
|
|
|
Oh! A lecture! 
You forgot only two very important elements of a lecture:
1) Somewhere in the middle you must say this, best after you have confused most of the audience:
"Obviously (something obscure) is (some even more obscure property).
2) At the end you must mention that these only were the essentials and say something like this:
"I leave (some terribly complicated case) as an exercise for you."
I have lived with several Zen masters - all of them were cats.
|
|
|
|
|
Well then how about this: I'll leave the calculation of the actual probability distribution as an exercise.
|
|
|
|
|
I have not done that in a long time.
I have lived with several Zen masters - all of them were cats.
|
|
|
|
|
I was waiting for the explaination how I can use this code I can cut and paste to break Las Vegas.
Installing Signature...
Do not switch off your computer.
|
|
|
|
|
Here you go:
public void BreakLasVegas(MissileLauncher Launcher)
{
if(MissileAcquireAndCommandCheck == Enums.MissileStatus.Go)
{
if(SetTarget("LasVegas") == Enums.MissileStatus.Go)
{
if(CheckSecurityLocksAndAuthorization() == Enums.MissileStatus.Go)
{
Launcher.Launch();
}
}
}
}
I have lived with several Zen masters - all of them were cats.
|
|
|
|
|
CodeWraith wrote: I have lived with several Zen masters - all of them were cats.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
harold aptroot wrote: it does not choose a permutation with uniform probability across all possible permutations
You're assuming that you actually want a uniform probability. If you're displaying the results to a human, that's going to end up "feeling" less random:
Why 'random' shuffle feels far from random | The Independent[^]
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
It fails that even worse, since it's biased towards keeping elements in order, while humans are biased towards expecting "mixing".
|
|
|
|
|
Nice! I was quite young when given this problem. (It is true: I was quite young in 1980). The language was Fortran and the container was an array of integers. So I solved by looping over all indexes and unconditionally swapping current index with random index. As far as I can tell this (accidentally) does not have the same flaw as your example. (AB happens after zero and two swaps, BA happens after either one of the possible swaps).
But what I am really after is: for this operation would I be wrong if I said that an indexable array, with my teenage algo, would give better performance than a linked list with the above code?
... such stuff as dreams are made on
|
|
|
|
|
"Lecture," or not, I really appreciate being able to read this ! In your view is Fisher-Yates enough for us mere mortals ?
cheers, Bill
«While I complain of being able to see only a shadow of the past, I may be insensitive to reality as it is now, since I'm not at a stage of development where I'm capable of seeing it. A few hundred years later another traveler despairing as myself, may mourn the disappearance of what I may have seen, but failed to see.» Claude Levi-Strauss (Tristes Tropiques, 1955)
|
|
|
|
|
Fisher-Yates is fine, you can even write a lazy version that yield returns the elements as soon as they have been chosen (it's really a sequence of random choices out of "the set of item you haven't had yet", every choice is final). Of course one should then be careful about their source of random numbers, for example a freshly-seeded instance of System.Random only has at most 31 bits of entropy (fewer if seeded with the current time) which on large shuffles limits the set of possible outcomes.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
