We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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:
Lazy Sorting
You are viewing a single comment's thread. Return to all 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: