About the Series
First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.
Hole 8: Shuffle an infinite list
You should write a function or program which takes an infinite list as input and returns a shuffled version of that list.
About infinite I/O
There are several ways you can take input and produce output for this challenge:
- You can either take a list of positive integers, or a string representation thereof, or a string or list of printable ASCII characters (0x20 to 0x7E, inclusive). The output format must match the input format. I'll just refer to the data as "the list" from now on, regardless of which option you choose.
- You can read the list from an infinite standard input stream and write the output continuously to an infinite standard output stream. The solution should not depend on any particular value or sequence of values to ensure that the output stream is regularly written and flushed (e.g. you can't just write output whenever there's a
5
in the input list). Of course, if you read a string representation of a list, it's fine to wait until encountering the list separator. - In languages that support them, you can write a function that takes and returns a lazy infinite list or string.
- In languages that support them you may implement an infinite generator that takes another generator as input.
- Alternatively, you can write a function which takes no arguments and returns one output value each time it is called. In this case, you can assume that a function has been defined which takes no arguments and returns the next input value each time it is called. You may freely choose that function's name.
You may assume that your program runs forever and that infinite memory is available. (It's possible to solve this with a finite amount of memory, but what this means is that you're allowed to leak memory.)
About the randomness
For any value v which is read at a position i of the infinite input, there must be a positive probability for it to end up in any of the positions i-9 to i+9 of the infinite output (unless that position would be negative). These probabilities don't have to be the same for different output positions or even for different input positions. It's fine if your solution can also shuffle the values to other position that are further away.
Hence, it's not necessary that your solution can shuffle the first value very far down the list, or that it can shuffle a very late value up to the first position, although it's fine if it does, as long as all positions 9 steps from the input are possible.
E.g. if you took the following string as input, the ___
indicates all the positions the X
must be able to end up in the output:
___________________
abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...
If your language lacks a built-in random number generator or you don't want to use it, you may take an additional seed value as input, and implement your own suitable RNG using the seed. This page may be helpful for that.
Regardless of the actual distribution your solution uses, it must almost surely produce the next value after a finite (but arbitrary) time.
Please include a short explanation about how your implementation satisfies these requirements.
Scoring
This is code-golf, so the shortest valid answer – measured in bytes – wins.
Leaderboard
The first post of the series generates a leaderboard.
To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:
# Language Name, N bytes
where N
is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)