I have a set $S=\{1,2,3,\dots,m\}$ and a (not necessarily 1:1) function $f$ mapping $S\rightarrow S$. I now seek a function $g$ (which also may be taken to map $S\rightarrow S$, as we might prove) that is order-preserving as such: $\forall{x_1,x_2}|f(x_1)<f(x_2)\Rightarrow g(x_1)<g(x_2)$. E.g. $g=f$ always works. Note that if $f(x_1)=f(x_2)$ we have some freedom in $g$.
Example: $f={1\rightarrow 2,2\rightarrow 1,3 \rightarrow2}$ or short $f=212$. Then $g_1=212,g_2=213,g_3=312,g_4=313,g_5=323$ is a complete list of valid $g$ for this $f$. Now in my problem for $g$ only order matters, so effectively $g_2\neq g_1=g_4=g_5\neq g_3\neq g_2$.
I now would like to check a few conjectures and could use a "random $g$" generator. I probably could write one myself very quickly that picks a random $g_i$, but as you see from the example, I rather would prefer one that lumps together equivalent $g$ and picks an equivalence class with equal probability.
Any ideas (I already have some very vague ones) to do that?
Say a function is packed if its set of values is $\{1,\ldots,k\}$ for some $k$. Each equivalence class has a unique packed representative. So your task is to choose in an identically distributed way a packed function $g$ satisfying your condition.
Consider the fibers of $f$ (a fiber is $f^{-1}(i)$ for some $i$). It is enough to create the function fiber by fiber and then stack the result in a packed way. For each fiber of $f$ the problem is choose in an equally distributed manner a packed function on the fiber (without any other condition). An inefficient way to do it is to choose randomly a function and if it is not packed, choose randomly another function, again and again until it is packed.