Randomising a stream

What would the most efficient way of randomising a sequence of unknown length whose elements are presented one by one be?

For instance, 'collect the whole lot, then shuffle' is the naive way, but there ought to be something cleverer.

A simple method is to swap a[n] with a[Random(1, n)] (using 1-based arrays). This seems pretty efficient, also.

Cheers,

If you know what symbol set the sequence is derived from, then simply generate (on the fly) a random 'one-time pad' and XOR each symbol from the sequence with the next symbol from the pad.

You have to remember the pad if you want to reconstitute the sequence of course.

What I think you are considering is this...

You, Allen, and Betty are sitting in a room. Allen has a deck of cards with N different symbols. You don't know what N is (in fact, Allen has his back turned to you, so the deck is hidden). He hands you the top card, and you must decide whether to hold onto that card for a while, or pass it along to Betty.

Allen then hands you another card, and you must make the same decision, though you have an additional choice of choosing the previous card to pass along. This continues, with you choosing at each step which, of those cards you hold, to pass along to Betty.

After Allen passes you the final card, he tells you that's all of them. You continue passing cards to Betty until you have no more.

You're goal, if I understand it right, is to find some method that passes the cards to Betty in a random order, so that any order is as likely as any other. A simple algorithm would be to wait until you have all the cards, then shuffle them, but you seek something better.

Regardless of the algorithm you come up with, in the worst case you will have to collect all the cards before passing a card to Betty. This is becasue the final card you receive you have probability 1/N of being the first card you pass. Further, until you know what N is, I don't think you can make a fair decision on whether to pass any of the cards you have (is there a way to prove this statement?). If that's true, I don't think there's any better way to do this than to just wait for all the cards, and shuffle them.

Bob H

If you do it the other way round (choose an existing item and move it into a new slot, then add the new item into the gap) then you get slightly less randomness. In particular, the last item to arrive will never be placed in last position.

Why can't I hand each card to Betty with instructions 'put this on top of the deck?', or 'put this 3 cards from the bottom', or 'I've already handed you 27 cards, put this one below 12 of them and above 15'. If Betty has n cards, and I am handing her the n+1th card, I should instruct her to place it in any ordinal place between 1 and N+1 inclusive.

I don't hold the whole deck, and I never shuffle.

This definitely works...stepping through the first few iterations makes it obvious:

A

BA AB

CBA BCA BAC CAB ACB ABC

all equiprobable

The only drawback to this method is that Betty now knows the entire order, so you haven't performed a useful randomization from her perspective. After you've given Betty the last card, she can hand off the deck to Charlie after performing one insertion. Charlie is now the first person to hold a random deck. The same limitation still applies: the input stream must finish and be buffered before the output stream can begin. This method does allow the majority of the work to occur while waiting for the input, which is what I think Martin was looking for.

Cheers,

Your computer (server) is simultaneously randomizing thousands of sequences, sending each one to a different computer (clients). The server can pick random numbers according to Geoff Bailey's algorithm, but the memory load is better distributed among the workstations.

This is a standard generic client-server design, with trade-offs between the server's speed and memory, the client's speed and memory, the network's speed, a minimum server load due to centralized data storage, and the complexity of writing the programming. A more complex form involves three levels - data server, logic server, and client - with similar trade-offs.

Nice one. I was thinking of something along the lines of the particle physics setup I worked with in grad school, where the machine that processed the data in real time didn't have the capacity to store it all.