Programming puzzles: processing lists!
|
06-06-2017, 01:44 PM
(This post was last modified: 06-06-2017 01:46 PM by pier4r.)
Post: #129
|
|||
|
|||
RE: Programming puzzles: processing lists!
So I was using the LSHF (list shuffle) command from the library of David.
I was curious how solid it was in shuffling the list, since I do not know the algorithm (any chances to share the idea?). So I created the following program: Code:
Now if I'm not mistaken, the chance of an element to end up in a position should be 1/n . Therefore the chances of an element to end up exactly in the original place, should be \( \left (1 - \frac{1}{n} \right )^{n-1} \cdot \left ( \frac{1}{n} \right ) \) . Since there are 'n' original elements, I can sum this term 'n' times. Then the chances that 2 elements ends up in exactly their original place are \( \left (1 - \frac{1}{n} \right )^{n-2} \cdot \left ( \frac{1}{n} \right )^{2} \) The amount of times this can happen are all the possible combinations of 2 elements, so \( \binom{n}{2} \) If I continue and pack this in a formula, plus I consider the resulting matches between the original list and the shuffled list (so I want the expected value of the number of matches), I have: \( \sum_{i=1}^{n} \left [ i \cdot \binom{n}{i} \cdot \left (1 - \frac{1}{n} \right )^{n-i} \cdot \left ( \frac{1}{n} \right )^{i} \right ] \) Once again, if I am not mistaken, this should average (thanks 50g) to 1 match if n=100 . And my test found out that my expectation through formulas seems to match the expectation through computation. So LSHF seems to work very well. Now I'm interested how it works. David could you explain the procedure behind LSHF ? Side note: it is possible that I made a lot of errors together, and by coincidence I got the same result. Wikis are great, Contribute :) |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)