Pseudo-randomly selecting and generating a permutation in O(1) space

I have a piece of code where I have to look in a bunch of vectors for the first element which satisfies a given predicate. I have to do this multiple times, and as there are multiple elements which satisfy my predicate, I'd like to somewhat randomize the order in which I check, so to give everybody a fair chance of being discovered.

At the same time, I'd like this to be as performant as possible, so I really don't want to shuffle/allocate or anything of the sort.

This requirements have sent me into a spiral of random number generation, linear congruential generators, LFSRs, Xorshifts, criptography, but I'm having a hard time figuring a good solution out.

I realize that picking a permutation truly randomly is impossible. What I'm looking for is a generator which I can pass

• N
• a seed
• some number of random bits (in the form of number parameters generated from a separate PRNG)

and it will cycle through one of the permutations of N elements (picked pseudo-randomly).

This answer provides what I think could be a good starting point; a generator for 16 bits in the form of

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf 

Which one can iterate over discarding any number < N. I like this since it does not require me to find a prime number, only the next highest power of 2 which is fast with bit-fiddling. I have played with this and I have a generator of the form

P(x) = ((x ^ (next_pow2 - 1)) ^ (x << z) + y) & (next_pow2 - 1)

Picking z and y randomly gives me different permutations. However, I don't understand exactly how this works, whether it can be improved, and in what range y and z should be to be as fair as possible (since changing parameters will result in duplicating some permutations).

Could anyone point me out whether there's a better solution, and what to read exactly to learn more? This field looks terribly complicated for a novice, and I don't know where to start.