Random Permutation problem

[Guest]

Hi! I'm trying to solve this problem found online... does anyone know how to do it? In particular the third point
I'd be happy to compare the solutions of the first two points too!

problem.png (365.11 KiB) Viewed 1167 times

[Guest]

I asked this on this sub a few years ago and got some interesting discussion but not much I could use. The issue has come around again and I thought I'd give it another try.

The application is a shuffle feature like you'd use on an MP3 player - let's say you have 1000 tracks and you want to play them in random sequence, not repeating a track until you've played all of them.

That's easily done with a Fisher-Yates shuffle, but that requires memory to store the result - in this case, much more than is available.

What I want is a function that will take a seed value, a total number of items, and an index n, and return the nth item in a random permutation. The system can spare maybe a couple hundred bytes of RAM during the calculation, but much less than that for any persistent state.

Wikipedia says this falls under format-preserving encryption and has some examples, but they seem too resource-intensive or beyond my skill level to implement - I have no idea how to construct a Feistel network.

If the number of items is a power of two you can simply use a block cipher with a block size matching the domain. That would be ideal - I have XXTEA available already, but its block size is far too large.

The HPC-Tiny cipher with the block size set just large enough for the domain would be better, but using it with cycle walking could still take thousands of iterations.

Any suggestions? This is mostly to scratch an itch and find a better way to do things - it's absolutely not critical; I'm just shuffling patterns on an LED hula hoop. It certainly doesn't need to be particularly secure, it just needs to be efficient, and I keep thinking there has to be a better way to approach this.