If, in addition to R, you are also not tied to a specific P, we could override the permutation function to facilitate a possible answer. The newPerm function, below, will rearrange the list with respect to R with the same consistency as the permutation function, which is "indexed into".
The example below is not optimized for efficiency (e.g. ranking / unlocking can be done in O (n)). The last two lines of output compare the overridden permutation function with the index permutation function - as you can see, both of them generate the same number of unique permutations when compared with a set of permutations. Function f would be the answer to the question.
Haskell Code:
import Data.List (sort,permutations) import Data.Maybe (fromJust) sortedPermutations = sort $ permutations [0,1,2,3,4,5,6] rank p = fromJust (lookup p rs) where rs = zip sortedPermutations [0..] unrank r = fromJust (lookup r ps) where ps = zip [0..] sortedPermutations tradPerm ps = foldr (\ab -> s!!a : b) [] p newPerm ps = unrank (f (rank p) (rank s)) f r1 r2 = let l = r1 - r2 in if l < 0 then length sortedPermutations + l else l
Output:
*Main Data.List> unrank 3 [0,1,2,3,5,6,4] *Main Data.List> unrank 8 [0,1,2,4,5,3,6] *Main Data.List> f 3 8 5035 *Main Data.List> newPerm [0,1,2,3,5,6,4] [0,1,2,4,5,3,6] [6,5,4,3,0,2,1] *Main Data.List> rank [6,5,4,3,0,2,1] 5035 *Main Data.List> length $ group $ sort $ map (tradPerm [1,2,5,0,4,3,6]) sortedPermutations 5040 *Main Data.List> length $ group $ sort $ map (newPerm [1,2,5,0,4,3,6]) sortedPermutations 5040