Geek Answers Handbook

Sort with stochastic comparisons

Given the list where for each pair of elements (A, B) the probabilities P (A> B), P (A <B) and P (A = B) are known, how do you determine the most likely sorted permutation?

+6
source share
2 answers

Let P(A=B) be ignored (we can say that it is evenly divided into <,> and changes them to <=,>= ).

Now let's look at a similar, but intuitively easier problem:

  • find the best destination such that P(arr[0]<arr[1])*...*P(arr[i]<arr[i+1])*...*P(arr[n-2]<arr[n-1]) is maximal.
  • This is a simpler problem, since now we only consider adjacent elements (and not, for example, P(arr[0]<arr[n-1]) - we use “less” information. [No proof atm].

Now we strive to maximize the probability, which is equivalent to maximizing:

 log{P(arr[0]<arr[1])} + ... + log{P(arr[n-2]<arr[n-1])}

Which in turn is equivalent to minimization:

 -log{P(arr[0]<arr[1])} - ... - log{P(arr[n-2]<arr[n-1])}

This is a TSP with weights around the edges:

 w(v,u) = -log(P(v<u))

However, TSP is NP-Complete, and if the missing evidence-based hypothesis is incorrect (still thinking about it ...) - this means that there is no known polynomial solution to this problem, or at least only elements adjacent to it.

+6
source

I think the easiest way to do this is to click items in the priority queue. Using these 3 probabilities, one with the highest probability of being the biggest is always at the top. A pop that pops up the next in height. Keep popping until you're done. I think this approach will work

0
source

More articles:


All Articles