Bubble sort quiz: why the result is not the same?

[lupoalberto]

here the math proof: (i continue not understand why our results are different from 1/14880).

https://www.cut-the-knot.org/Probability...orts.shtml

[ljmetzger]

Thank you for providing the theoretical solution.

The original question was:

1)Find the probability that the number that begins as r20 will end up, after one bubble pass, in the 30th place.
2)Find the probability that the number that begins as r20 will end up, after second bubble pass, in the 30th place.

We interpreted the above (I think correctly) as two independent questions. From the solution, the intent was really:

What is the probability of question 2, if question r20 is in the 30th place after pass 1.

Here is the code for my solution, which now matches the theoretical results.

import random

def bubble_sort_one_pass(a, pass_number):
    n = len(a)
 
    # Subtract 1 because arrays are '0 based' and Pass 1 uses index 0
    i = pass_number - 1
    for j in range(0, n-i-1):
        if a[j] > a[j+1] :
            a[j], a[j+1] = a[j+1], a[j]
    return(a)
    
def generateList():
    L = []
    remaining = [i for i in range(1,41)]
    while len(L) < 40:
        random_N = random.choice(remaining)
        L.append(random_N)
        remaining.remove(random_N)
    return L
 
N = 1000000
totalOnePass = 0
totalTwoPass = 0
for i in range(N):
    L = generateList()
    f = L[19]

    pass_number = 1
    L = bubble_sort_one_pass(L, pass_number)
    if f == L[29]:
        totalOnePass += 1
        #
        pass_number = 2
        L = bubble_sort_one_pass(L, pass_number)
        if f == L[29]:
            totalTwoPass += 1
            
print("Probability after One Pass is {} {} {} {} ".format(totalOnePass, float(N/930  ), float(totalOnePass / N), float(1/930)))
print("Probability after Two Pass is {} {} {} {} ".format(totalTwoPass, float(N/14880), float(totalTwoPass / N), float(1/14880)))

Output edited for prettyprint

Output:
                              Actual Theoretical   Actual       Theoretical
                              Counts      Counts   Probability  Probability
Probability after One Pass is   1109      1075.3   0.001109     0.001075
Probability after Two Pass is     64        67.2   6.400e-05    6.7202e-05

Lewis