# Efficient permutation of given ranking that preserves given distance

Ranked Biased Overlap (RBO) is a metric for comparing two rankings and is used when the sizes of the given rankings are different and/or the elements that they carry are not the same. Ranked Biased Distance (RBD = 1 - RBO) is the distance metric emanating from RBO. A simple demonstration of the metric can be found here, along with a link to an implementation in Python.

Currently, I want to find an efficient way of calculating the "inverse" of RBO. Typically, RBO is a function like the following:

double rbo(List<A> rankingA, List<B> rankingB)


The double value returned, is the RBO value of rankings rankingA and rankingB. I want to implement the following method:

List<A> generateRanking(List<A> rankingA, double rbo)


which given a ranking (rankingA) and an RBO value (rbo), it generates a random permutation of rankingA, that its RBO value with the initial ranking is rbo. Apart from a trial-and-error approach, in which I randomly permute rankingA until I meet rbo, can you think of a better way (more computationally efficient) of doing so?

Thank you

• Welcome to CS.SE! 1. Can you give a self-contained definition of the RBO metric, in the question? The link you provide is to a paper that doesn't appear to be freely available to the public. 2. Do you require that the random permutation be uniformly distributed over all permutations whose RBO value with the initial ranking is rbo? Or can it be any random distribution (not necessarily uniform)? – D.W. Jul 5 '17 at 18:39
• @D.W. thank you for the welcome message. 1. I have edited my question to contain a link to a blog post that contains a visual explanation, along with python code of RBO. 2. It can be any random distribution, since uniform search might end up too computationally expensive. – nick.katsip Jul 5 '17 at 18:59
• In particular, can it be a random distribution supported on a single element? – Yuval Filmus Jul 5 '17 at 19:01
• Well, it can be, but I am afraid that might be too limiting. For instance, the desired RBO might be too low or too high with a single element permutation. But, I assume that would be a good place to start – nick.katsip Jul 5 '17 at 19:08
• So based on your comments, it sounds like we can rephrase your question as: "given an initial ranking and a RBO value, output any permutation whose RBO value with the initial ranking is the desired value". It appears there's no need for the output to be random in any sense; it can be arbitrarily chosen by the algorithm. If I haven't understood correctly, I hope you'll correct that and clear up my confusion. – D.W. Jul 5 '17 at 20:01