2

I have p items (let's assume p=5, items={0,1,2,3,4}). I need to be able to iterate over them in a random order, but without repeating them (unless all were visited) while maintaining only as small seed-like metadata as possible between the iterations. The generator is otherwise stateless. It would be used like this:

Initialization (metadata is long in this example, but it could be anything "small"):

long metadata = randomLong()

Usage:

(metadata, result) = generator.generate(metadata) return(result)

If it works properly, it should continuously return something like 3, 1, 0, 4, 2, 3, 1, 0, 4, 2, 3...

Is that possible?

I know I could easily pre-generate the sequence, then metadata would contain whole this sequence and an index, but that's not viable for me, as the sequence will have thousands of items and the metadata must be slim.

I also found this, which resembles what I am trying to achieve, but it's either too brief or too math-y for me.

Added: I am aware of the fact, that for p=1000, there are 1000! ways of ordering the sequence, which would definitely not fit into a long, but both "having metadata something bigger than long" and "generator may be unable to generate some sequences" is OK for me.

Improve this question
0

1 Answer 1

Reset to default
2

I would, as a base, use Fisher-Yates algorithm. It is able to construct a random permutation of a given ordered list of elements in O(n). Then the trick could be to construct an iterator that shuffles an internal list of elements and iterate through it, and when this internal iteration ends, shuffles again and iterate on the result...

Something like:

function next() -> element { internal data: i an integer; d an array of elements; code: if i equals to d.length { shuffle(d); i <-- 0; } return d[i++]; }
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

actually, by pre-generating the sequence I meant also having to store it in the metadata.. I didn't realize I could just re-generate it using the same seed every iteration, that would work just fine!
This is a fine solution in general, but I interpreted OP's question to specifically rule it out due to there being "thousands of items".
Yea, I am sorry. I should've been more specific. Computational time is no problem, just the metadata size is constrained.
@Erlik I also don't understand since in this case the random generator must keep the pre-generated sequence or, as you say re-generate it at each extraction, that will anyway allocate a large data array (at least size k for the k-th extraction), so what's the point to have a small metadata and a large memory usage? Not to contest the solution, just to understand the problem that you are trying to solve!
@Rocco the size constraint of metadata comes from the fact, that it's needed for a (Rasa based) chatbot, where it doesn't really matter if the computation takes 1ms or 10ms / 1kB or 1MB, but the crucial part is how much data needs to be stored (in order to capture the state), because that's what's passed among all Rasa and java components and kept in the DB for each conversation..
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.