fork download
copy 
  1.  
  2. def next_permutation(L):
  3.     '''
  4.     Permute the list L in-place to generate the next lexicographic permutation.
  5.     Return True if such a permutation exists, else return False.
  6.     '''
  7.  
  8.     n = len(L)
  9.  
  10.     #------------------------------------------------------------
  11.  
  12.     # Step 1: find rightmost position i such that L[i] < L[i+1]
  13.     i = n - 2
  14.     while i >= 0 and L[i] >= L[i+1]:
  15.         i -= 1
  16.  
  17.     if i == -1:
  18.         return False
  19.  
  20.     #------------------------------------------------------------
  21.  
  22.     # Step 2: find rightmost position j to the right of i such that L[j] > L[i]
  23.     j = i + 1
  24.     while j < n and L[j] > L[i]:
  25.         j += 1
  26.     j -= 1
  27.  
  28.     #------------------------------------------------------------
  29.  
  30.     # Step 3: swap L[i] and L[j]
  31.     L[i], L[j] = L[j], L[i]
  32.  
  33.     #------------------------------------------------------------
  34.  
  35.     # Step 4: reverse everything to the right of i
  36.     left = i + 1
  37.     right = n - 1
  38.  
  39.     while left < right:
  40.         L[left], L[right] = L[right], L[left]
  41.         left += 1
  42.         right -= 1
  43.  
  44.     return True
  45.  
  46.  
  47.  
  48. #-------------------------------------------------------------------
  49. #-------------------------------------------------------------------
  50.  
  51. def example():
  52.     count_in_church = 0
  53.     total_permutations = 0
  54.     k = 10
  55.     L = k*[0] + k*[1]
  56.  
  57.     while True:
  58.         total_permutations += 1
  59.  
  60.         # check if bride steps into church by checking if
  61.         # the number of ones exceeds the number of zeros
  62.         cnt_0 = 0
  63.         cnt_1 = 0
  64.  
  65.         for c in L:
  66.             if c == 0: cnt_0 += 1
  67.             else: cnt_1 += 1
  68.  
  69.             if cnt_1 > cnt_0:
  70.                 count_in_church += 1
  71.                 break
  72.  
  73.         if not next_permutation(L):
  74.             break
  75.  
  76.     print("number of times bride entered church: ", count_in_church)
  77.     print("total permutations:", total_permutations)
  78.     print("probability:", count_in_church / total_permutations)
  79.  
  80.  
  81. #----------------------------------------------------------------
  82.  
  83. if __name__ == "__main__":
  84.     example()
  85.  
Success #stdin #stdout 0.24s 28384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
number of times bride entered church:  167960
total permutations: 184756
probability: 0.9090909090909091
https://ideone.com/5ZCbQZ
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!