It appears that this is equivalent to the question of the complexity of the discrete logarithm problem, so I think this question is in general an open problem and ought to be retagged and treated as such.
As Maarty Isaacs commented $$f_p(n)=np\mod q.$$ To say that the order in which the elements reappear is of a random nature is to say that $np\mod q$ is of high complexity, which is the same as the complexity of its inverse.
In other words, given a cyclic group $G$, a generator $g$ and an element $f$, the question is:
How difficult is it to find an integer $n$ such that $f=g^n$?