• + 0 comments

    If P is already sorted, return 0. Otherwise, compute the number of permutations of P considering that it is possible to have repeated elements. The formula for this is n_pr = N!/(n1!n2!...*nk!), considering that N is the total number of elements in P and n_k is the number of copies of the k-th unique element. Notice that the probability of selecting the ordered, non-decreasing permutation is given by p = 1/n_pr. Now, let's calculate the expected number of minutes (steps) to find the sorted sequence. This is done by the following equation: E = p * 1 + (1 - p) * (E + 1). If we are happy to find it next, then it takes just one step. If not, we need to add up one step and start again. But: E * (1 - (1 - p)) = p + (1 - p) = 1/p = n_pr So the idea is to find n_pr as fast as possible, which is done iteratively:

    def solve(P):
    
        if P == sorted(P):
            return 0
            
        counts = [P.count(i) for i in list(set(P))]
        n_perm_w_repetitions = int(math.factorial(len(P))/math.factorial(counts[0]))
        for c in counts[1:]:
            n_perm_w_repetitions = int(n_perm_w_repetitions/math.factorial(c))
        ev = n_perm_w_repetitions
        return "%.6f" % round(ev)