Post Reply 
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:


    @ using the library from davidM
    @ want to check wheter the shuffling is good enough or not.
    @ if that check is possible.
    @ The expected value of matches given a base list of 100 elements
    @ should be, if I am not mistaken, '\GS(I=1,100, IxCOMB(100,I)x(1-1/100)^(100-I)x(1/100)^I'
    @ let's see if a simulation fits
      {} "basePerm" DROP
      {} "lshfPerm" DROP
      0 "sumNoMatches" DROP
      @local var
        listSize seqList 'basePerm' STO
        1 iterations
          basePerm LSHF
          2 @taking one element from 2 lists
          \<< == \>>
          @here we have a list with 1 or 0 according to match or not match
          @ we add 0 to avoid complains
          0 +
          @we count how many matches there were
          @we save the result
          'sumNoMatches' STO+
        iterations "iterations" \->TAG
        listSize "listSize" \->TAG
        sumNoMatches iterations /
        "avgNumMatches" \->TAG

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 :)
Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 06-06-2017 01:44 PM

User(s) browsing this thread: 2 Guest(s)