2

Let's say I have a sequence of items of unknown length, n. I want to randomize the order of this sequence without having to go through the entire sequence. Are there any algorithms that can do this?

Example:

I have 10 items in my sequence: A B C D E F G H I J (though I don't know that I have 10). At the end of my randomization it would have ended up as E G F B A I C D J H.

If I only wanted to know the first 3 random elements, I would get E G F, and since G is the furthest element in the original sequence, I would never have to read the sequence past G.

My algorithm would, somehow, look at A and realize that it randomly belongs past the first 3 requested elements, it would then look at B and realize the same, ..., it would look at E and realize that it needs to randomly be the first element so it adds it to a return buffer as element 1, then F randomly should be the third element, so it adds it to a return buffer as element 3, then it hits G and adds that to the return buffer as element 2 and it completes. It never even looks at where H, I, or J should go.

Improve this question
8
  • 2
    How did you get the original randomization without knowing the length? How do you make sure that your randomization actually could include the last element without getting to it? ANd how do you know there are no more?
    – cdkMoose
    Jul 30, 2015 at 21:25
  • 1
    That was food for thought, that's why I didn't post as an answer. Trying to give ideas about why you would or would not need to know the length, or at least knowing the end of the line. I suspect this will be closed as too broad, so I am trying to help you analyze it yourself.
    – cdkMoose
    Jul 30, 2015 at 21:38
  • 2
    If you actually want 'pick 3 elements uniformly at random from an arbitrary sequence without knowing the sequence length', this is impossible (each element should have a probability of 3/n of being picked, which you can't know without knowing n). If you want 'pick 3 elements uniformly at random from a sequence of known length without necessarily enumerating the whole sequence', this is doable.
    – AakashM
    Jul 31, 2015 at 8:27
  • 1
    I suppose the uniformity requirement must be dropped for the question to be answerable.
    – rwong
    Jul 31, 2015 at 9:31
  • 2
    Here is a question that you should answer before you ask this one: Can I get the second to last element in a list of unknown length?
    – Daniel
    Jul 31, 2015 at 22:12

2 Answers 2

Reset to default
7

A common way to read data coming into the computer is to buffer it from a stream.

Streams sometimes have an undefined length. All we know for sure is we can "get next character from stream".

Normally we'd add the character from the stream to the end of the buffer (think FIFO queue).

The size of the buffer doesn't necessarily have to be the size of the stream, IF we are simultaneously emptying the buffer (i.e., reading from it to pass the data somewhere else) at the same time. Your stream might produce a single character at a time, but you might want to "buffer them up" until you have a complete line. You could pass a 100MB text file through a 1KB buffer as long as no single line in the file was over 1,024 characters long.

Here's the clever bit

What if, instead of appending the next character from the stream to the end of the buffer, we instead randomly insert it anywhere in the buffer?

An important limitation

No item can be displaced from its original location by more than the buffer size. If you have a buffer size of 200 and you have 1,000 elements, you will never "randomly" pick the 999th element first. Having a really big buffer would help.

Ideally, having a buffer bigger than your input stream would reduce this to a much simpler problem.

Improve this answer
4
  • 4
    The obvious flaw with this system is that no item can end up displaced from its original location by more than the buffer size, which makes it hard to consider the result as being "randomised". It might be good enough for some applications, but I wouldn't want to rely on it in any area where somebody predicting the next item could break the validity of the application (e.g. for gaming purposes it could allow players to cheat to some degree).
    – Jules
    Aug 1, 2015 at 8:28
  • 1
    @Jules Sigh. Why aren't obvious flaws obvious when writing the answer? You are completely correct. For this application, the bigger the buffer the better - but it's still flawed.
    – Dan Pichelman
    Aug 1, 2015 at 14:39
  • 1
    It is not a flaw in the algorithm; it is a limited applicability. The question does not have a theoretically flawless answer. Instead, the question only asks for a "useful enough" algorithm given the application's requirements. Choosing a large-enough buffer will meet at least some application requirements, so I wouldn't say it's a flaw.
    – rwong
    Aug 1, 2015 at 19:54
  • @Dan Could you add these comments to your answer? They are very important and comments may disappear.
    – Jan Doggen
    Aug 4, 2015 at 8:26
2

Here is one such scheme. It is only a brief idea, I did not check it carefully for potential fallacies.

Before starting, we perform the following configuration:

  • For every natural number N (1, 2, 3, ...), choose a bit shuffling function for N bits.

Procedure for converting query integer I to response integer J

  1. Given a query integer I, convert it into binary representation.
  2. If the query integer I is zero or one, there is nothing to do; return it as J.
    • This is a limitation of this scheme.
  3. Find its highest-bit-set (the most significant bit that is a "one"). Choose N so that there are N binary digits below the highest-bit-set.
  4. Look up the bit shuffling function for N as configured above.
  5. Apply this bit shuffling function to the lowest N bits of the number. Remember that the highest-bit-set is not being shuffled; it must keep its value of "one".
  6. The new number (where the highest-bit-set is kept but the lower bits had been shuffled) is returned as response integer J.

Analysis.

  • Let's say the query integer I can be represented in 6 binary digits. (example: "100101"). The maximum possible response integer J given I is also 6 binary digits (example: "111111"). Therefore, the upper bound for J is pow(2, ceil(log2(I + 1))) - 1.

Refinement prompted by @amon's comment.

The N-bit bitwise-permutation function can be replaced by a general 2**N integer permutation function (one-to-one integer mapping). This way, when the N-bits are all zero, it will not be stuck with an all-zero output due to the bitwise permutation.

There are lots of shortcomings in this scheme. The purpose of this answer is to encourage more discussions and possibly more practical answers.

Improve this answer
2
  • If I understand this answer correctly (assuming shuffling=reordering), this algorithm deterministically transforms an input number into an output number with the property that both numbers have the same number of set bits, and that the output number is bounded within a specific range. Notably, it will return the number itself when all less significant bits are all zero xor one, e.g. in 0, 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, …. It does not lazily yield randomly picked elements from a stream, and it is certainly not “random” in any usable sense of the word.
    – amon
    Aug 1, 2015 at 19:14
  • @amon you are correct. There are many shortcomings. Notice that the original question can't possibly have a truly "uniformly random" answer (in the strictest sense). Also, earlier in the discussion there was the consensus feeling that this question is unanswerable (even after removing the uniformity requirement). My answer provides a crude example that one can still find some usefulness even if it is theoretically far from perfect, thus steering the consensus in the optimistic direction. I do expect others to provide improvements.
    – rwong
    Aug 1, 2015 at 19:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.