def next_permutation(L):
    '''
    Permute the list L in-place to generate the next lexicographic permutation.
    Return True if such a permutation exists, else return False.
    '''
     
    n = len(L)
 
    #------------------------------------------------------------
 
    # Step 1: find rightmost position i such that L[i] < L[i+1]
    i = n - 2
    while i >= 0 and L[i] >= L[i+1]:
        i -= 1
     
    if i == -1:
        return False
 
    #------------------------------------------------------------
 
    # Step 2: find rightmost position j to the right of i such that L[j] > L[i]
    j = i + 1
    while j < n and L[j] > L[i]:
        j += 1
    j -= 1
     
    #------------------------------------------------------------
 
    # Step 3: swap L[i] and L[j]
    L[i], L[j] = L[j], L[i]
     
    #------------------------------------------------------------
 
    # Step 4: reverse everything to the right of i
    left = i + 1
    right = n - 1
 
    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1
             
    return True



#-------------------------------------------------------------------
#-------------------------------------------------------------------

def example():
    count_in_church = 0
    total_permutations = 0
    k = 10
    L = k*[0] + k*[1]
 
    while True:
        total_permutations += 1

        # check if bride steps into church by checking if
        # the number of ones exceeds the number of zeros
        cnt_0 = 0
        cnt_1 = 0
          
        for c in L:
            if c == 0: cnt_0 += 1
            else: cnt_1 += 1

            if cnt_1 > cnt_0:
                count_in_church += 1
                break
        
        if not next_permutation(L):
            break

    print("number of times bride entered church: ", count_in_church)
    print("total permutations:", total_permutations)
    print("probability:", count_in_church / total_permutations)
 
 
#----------------------------------------------------------------
 
if __name__ == "__main__":
    example()