# Random Golf of the Day #8: Shuffle an infinite list

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.

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.)

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.

## Scoring

This is , so the shortest valid answer – measured in bytes – wins.

The first post of the series generates a leaderboard.

# 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.)

• May we assume infinite time/memory available?
– user45941
May 13, 2017 at 20:36
• If the language does have something called a random number generator, are we really required to use it? May 13, 2017 at 20:44
• @Mego Infinite time, obviously. And infinite memory, yes as usual for challenges that require programs to process data forever (it's possible to solve this in finite memory, but I don't want to punish languages that are forced to leak memory). May 13, 2017 at 21:35
• @feersum I should probably specify the requirements of a self-built random number generator a bit more precisely, but I can't imagine implementing your own to be shorter than a built-in RNG in most cases? May 13, 2017 at 21:37
• @feersum I've clarified that part a bit and linked to our standard definition for randomness. May 13, 2017 at 21:57

# Python 3, 78 bytes

from random import*
l=[]
while[shuffle(l)]:l[9:]and print(l.pop());l+=input(),


Try it online!

Takes input from STDIN (one per line), prints to STDOUT.

Keeps a buffer l of up to 10 elements. The buffer is shuffled with each step. When its length is 10, the last element is printed and removed.

If an element happens to be printed as soon as it was inserted, it has skipped ahead of 9 other elements waiting in the buffer, so it appears 9 spots left. An element can wait in the buffer arbitrarily long, so its position can move any amount right.

There doesn't seem to be a nice way to produce and remove a random element from a list. Shuffling seems like overkill. It's 2 bytes longer to use l.pop(randint(0,9)) (which uses that the list has 10 elements).

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(l.pop(randint(0,9)))


It's no better to do x=choice(l);l.remove(x).A language with poprandom like

poprandom = lambda l:l.pop(randrange(len(l)))


could very cleanly do

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(poprandom(l))


# Befunge (quirkster flavor), 4 bytes

?,?~


, reads a character from the stream and pushes it onto the stack. ~ pops the top character from the stack (if present) and prints it. ? randomizes which command is executed next. So the algorithm here is "In an infinite loop, with equal probability either push a character or pop a character." I think this satisfies the requirements: a character can see arbitrarily many characters added above it in the stack, so it can move arbitrarily far to the right, and it can be printed when the stack is arbitrarily big, so it can move arbitrarily far to the left.

• Doesn't this output null bytes if the stack is empty? May 14, 2017 at 4:18
• The implementation I linked doesn't; I agree by the Befunge spec it should. May 14, 2017 at 12:44
• Funny, the browser eats null bytes. It calls its implementation of putchar("\0"), but FF purges it from the HTML: >> document.getElementById("output").innerHTML = "a\0b" >> document.getElementById("output").innerHTML "ab" May 14, 2017 at 21:53
• Aha, I wondered if something weird was happening in the browser. I guess my Chrome does that too. Well, that is a heck of a technicality then, but I guess it's more or less in the spirit of the site to post a solution that only works in some interpreters run in some environments. May 15, 2017 at 18:22

# C (gcc), 94 bytes

L;i;f(s){srand(s);int B[9]={0};for(L=0;;)L>9&&putchar(B[i=rand()%10]),B[L>9?i:L++]=getchar();}


Try it online!

Ok, a TIO link doesn't make much sense. For ease of testing, I created the following C program that will output random ascii characters, or repeat an string infinitely.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char** argv){
srand(time(NULL));
if(argc < 1) {
for(;;){
printf("%c", rand() % 95 + 32);
}
} else {
char* s = argv[1];
int i = 0;
for(;;){
if(s[i] == 0)
i = 0;
printf("%c", s[i++]);
}
}
}


This program will be referred to as iro.

## Program correctness

What I do here is read 9 values into a buffer. After this, random indices are chosen from this array and are outputted, then replaced by the next character in the stream.

# S.I.L.O.S, 149 bytes

b=1
lbla
x=15+b*15
b=1
lblb
queue 0 i
x-1
if x b
a=0
lblx
x=rand*2
queuePop 0
if x X
printInt m
a+1
b=15-a
if b x
GOTO a
lblX
queue 0 m
GOTO x


Try it online!

Essentially it keeps taking input (on the online interpreter through arguments, but on the offline official interpreter it will allow you type into the console (infinitely)) in blocks of 15 at a time (30 the first block).

It loads the input into a temporary queue and picks a lucky 15 (randomly, but not equally distributed in terms of probablity or distribution).

The rest remain in as new inputs fill the queue, the first input could be shuffled all the way to the end, (basically I think the characters follow a normal distribution). It's interesting to note that this program is only twice as verbose as python and perhaps "golfier" than Java.

To better see the results I have a non-compliant version which takes input as a string (however it can only take in 8,000 or so characters).

Try it online!

Just for fun, here is this post fed through the string version.

 [.L.Ooy" 9beS.I.S],"14 ts  b1
nly

=ll
x=1b 15   1
5b  a*b=  lb  rd#  + lb eaI O    e
x
ifquu
1 0x b
=

e
0
i lblxa -d*2
quu   x=rn
x Xea p0
pnInt o r   a
mf =   iePit
ba 1
GTO  1 f b x+ Oa

qe -lblX u0 m    GOOue
[rlT

tnn5 !I.STii][S.LO ie

htpsgthyx]:iub.om/jhujh.. tcraa.I.O.o /TytonieSu:wl/.L lnn!:tt/iS
[ in hsto.un/nuslprxRUCoDsio/]:e#NzZn6j4c/2xNQFnF7y0aLzkrosd9Dov2yxJNx774HBrgPUdi9CySI09sCLw5TJwB7jlB1XVeQFE7m1VMsIQvDOjBmdtME3umNzYXs9unFbqRamVDfUDw@RT3NHoL7/i04bz16DCoP4eulOU7jPD8OmYjATpynkuMDuBPYmtnIJzseyyhaNkMyQgXG2R782vqMDIiUm6Kq4Q3mJkxlUsR1rrldPw./l28Z SL.XS – IONuscOT "
senallyxMz.stiitkp ingN"
eestaint on heeInliinrprt (oe e  toghr tetgpnmntuon eruEuut r h ofi off,bhenecil inretea.atr  ialoks tirilw upeitfleptly ty  honso (e oote cenfine iwllbc 15 atly) nitloo  aim( te)nikfte3 firs bck)
hs 0It te
lodshipo alauttt.mpra quuet i reanicks a lck eooy d  randomyn p 15( u o equl,unbtty drbutedaynistinems oftrly ordisrprob ill abition h  ibttmin.Tet ri)
a nwit u ree nusfil th queusen
pte ftip,ae uldsfuesis ob hl rlelth weual  t tc hdyoend,f tbaaly thi an elnkhecarcthe(sc h o  noreiItrolwaaldibtio  lmiru.t' iereaf ) tsng tetntiottssht prasnon  hogIms only twieatisi s vroscpythonadprs a hbapolfi" e r n e ehanava.
tte s/"gt
obterelIe  tsvea non-omhTrehs  a plntvesion hcahihk ine teuts sriprics at rwvritcaw aa g(hoee n onl kein n00 orscat ,0  cter).

[Tyauoas  it onine!hrhrys:.ru]p//o/lsslo#jVd(tinnexi3E@KDpit/LrhtwXwVEUuscxPmJjFFCaNimMzlHiQEcMmdVIT7vqs8mNgxU3mD/J1AwX q/ivbao1j@nb4I6/m93655bThmb4cy5TUX3xvI018cZzrXItuO5B@NX5JD/HzyE@G@D5eqrGem3l0HPGRutZfpi2PzVA@d3CVRTm4zJxnZdcFSTEO0JOT9KhDI6byjnLhS0cNmGz7hJrTdAgORT8Ndvv7DgZSbJdkp9v5al8qMyNCb9tXe0ChrShXRTOt@7fFgV3zTkbVbsD@JpKina2oKgNVakjsjLCpD29u7l0XVRWalVTyArF1FqypQAxXb/BedqUqpJGOPVyxOjLj0jXup8cE277L2I6@lSowK5pA7nGldRBiJwyKxF6z2c3kW/sJ4EYBbbpSuBxs55nyI9sdnu@nJJeGqtKprGEUbc6NDGMjjO2tN/KuKTWh2WWbbRRLVaq/P6KqkoMNWGRgTQZLlbXfQI050bY0rz0xmzCVZ4vowjpV0dCmkDFq0VNa5GSDzVn5Qw7idwPTxu5xTAtLQCDN/YIApfAn4dsDmYksCqUU27sRggpzRK4SmdjmPUPQO4j5FmgHMFRWS2eI1CfA2YIcf7JlylFjdZypVTH0IJu4ZJHiUviyBFKqhrkCjgXAAB8d710NhHgDwcJksuvPPprcfzHPTaJGFX8OIExW/cBZjaPiY7a4WD6rTYmOouBVucROlwvuBJiHWdJQjjbobNGTd7M1P6z8dw/A@GU02hgjCcrjjQHkAdS6r7UjQ6wAPqB@sIgxkKcbZDixeWS6mn160CKQpn7aUwGLK22u9I0oX6YIwPMhFVaX5uYon0AyoNTCZvnmtilVhV3/pgTGc7r39lIS5PmqM/NGnUSLnTw9eTJ7qqrNQKsJHz@Tt8mDZVWKCKTkBro1PuQAksDdN1yaVGiVXElRW9i5M11cINmxNGYAg9TD7sxtEDI2OkKMaBXgvO5dOplUQQIdpb2w66NePBScMmEnAX8ydGSiiHlss@hOLZzInnIoTevRtEm/TGHWOkly5ljMK4FkgDDSWCWBW3YwmEVYCIBV@GMIg3TZtGwMFWXVxQwBb5iD6PfS7h7Sric1ib5ZYIvW6n3tlaK7/6@3OAHy4LjOuW@tzaBP3@mFbJpHsVsQKPfeui/o1@aBcbZ4TK96T8tp3QjeA1vDXMKBIqdK@HZs2vsMlQE36YmrBEnVRUvAGNuCt44e0RB0sL0MkNu1Q5wOwliTT2JQzVrOnHAmSXIU//sqjdG6jdT2r1v@@lGjouzkGWoD4zhnzJBxo0OT6OTbBDgeDFRnY8TMXZbMPdxsCtbXeUxIBqST4VRwkpbgwChBcJxMx6hLIVZhfuylDvF1l26Nbl3xRLgQnatSCMigx@PCT6lcG1ebdk/86UBUFp9UkxjoCGSJnlxMtUdHf6IjkMnil5aua9L@xXsdHEKW@8JpVqlgKsr12bAKG2Typfv@Yy4CkUydETWphcdmdpWq7egtxqP8pYI2rSaSuYBwW0tNTdXn4qcjnZ9JKhuVwaWRycwCWt247LSflsCHsB3u0KoLTQJzL1uMl0duij/IF7LCc5FSpIPW7gcjOYj@jQdpQHv0WUz/IbMhS0XmFiWm1i0cTbxXjsjLxt6nGmQNQoKfREklc8pTFyHub7jUg8TR4QrZ2w3YjaLWNi@FFerCnNgY0LqgrA6qkWg8H/7Pv6YhtqeZzvoB0yD5Wm1eLL1Vf/SouI0Q/fox7eQlXieZB1F1v2/in/btqyVPtubWhDIKH8WaTlry43N6HgOEzX5HOjv1@lamBeZlJpqJnG3B2LZe8sXUafdAcVvVjBBlqxbEThCdjpelc7YVuYXOqM8MyVV3iPxbqYu@nmbHnoKpK1Eww11sA9aiwN8kMe0ioVO7qnucL1A8wHJ4wTsdltrm3CC4bpCd5hMhyDGXSdGgdKvnCKUpNB9nH@wXLgu5iUEcfJbDKZFjx6gI9i8fCcUFiQXxeSbKnwhT6@v/I6yS/Ew9k@tgI68/lO@4jjx0PZBpSo5vWLCDi4zb@TJejQQPtvlgde98MDGJ4vUW3T@iJTA89gGhUJIgy@MDBpaz3s7PT2ZIwStVANsxpCmhghh68huncD0VdumQt0lT/Su6HW3kMLFfo/FphQ0QhtoZ5iRN/@hZ/DmHq8UZEgiblprekkw1I366fMhePmDclSxirOlYH2Hwe3fom3aoe1@yaQYwi5ZPd2FcITXO7cu9@6tiHZJc7lKSB8e3/mXx34xYH/8F@TUxx/5vs5yHsYBL4ekscycqT1BnuV19/ "SFE/iRAIL.O NqUXAm. T3zDreu).S –IOxs."d

• Your header may break the leaderboard - if you want to participate in the Random Golf of the Day competition it would be a good idea to use the standard format. May 14, 2017 at 9:10
• @wizzwizz4 fixed May 14, 2017 at 11:21

# Aceto, 24 bytes, non-competing

Non-competing because I had to fix a bug in the interpreter.

^

OYpO
r^!
?d0=   >


Takes an infinite stream of lines and yields them in a random order. Every element has a chance of occurring at any random point.

We start with a ? in the bottom left corner, which moves us in a random direction. If that is down or left, we get pushed right back.

If we're moved upwards, we read a value, shuffle the stack (Y), and jump back to the Origin.

If we're moved to the right, we duplicate the top stack value, push a 0 and test for equality (since we're reading strings, we can't ever have the integer 0). If the values are equal, that means we've reached the bottom of the stack (from which we don't want to print). We negate the comparison (!), and print only if () the things were not equal. Then we also jump back to the Origin.

# Ruby, 43 bytes

l=[];loop{l<<gets;l[9]&&$><<l.shuffle!.pop}  My original answer used a lazy-evaluated infinite list, but this is shorter. Oh well. # MATL, 11 bytes rEkN*?D}iT  Try it online! Port of histocrat's Befunge answer. Explanation: (Thanks to Luis Mendo for -1 byte)  T % Start do-while () .... true (T) rEk % 50-50 chance of outputting or inputting: % Random number between 0...1, multiplied by 2 and converted to logical. N % Check if there is anything on the stack to output *? % If there is anything on the stack and (*) we want to output: D % Output. Sadly, D errors when the stack is empty, requiring the N* }i % Else, input.  This outputs almost surely in finite time, and almost surely requires only finite memory. For completeness, here is a 15-byte version which keeps a 10-element buffer and outputs a random element from that: htnt9>?Yr&)wDT  I like this version for the very idiomatic (as far as golfing languages can be idiomatic) tn...Yr&), which pops a random element from the list and returns the list without that element. However, the particular logistics of this challenge add a lot of bytes (the required w for the display, the t9>? to check if the list is full enough...). # Alice, 7 bytes a&IdU,O  Try it online! This should work on an infinite input with infinite time and memory, but it's not so easy to test in practice :) ### Explanation a&I Push 10 characters from the input to the stack. d Push the depth of the stack. U Pop a number (d), push a random number in [0,d) , Pop a number (n), move the element which is n elements below the top to the top of the stack. O Output the character on top of the stack. Execution loops back to the beginning of the line.  At each iteration 10 characters are read from input and only one goes to the output, so memory usage increases linearly during execution. With a finite input this quickly reaches EOF, from which ten -1 will be pushed to the stack at each iteration. Trying to output -1 as a character has no effect, but it's unlikely that all the characters of the input will be printed in a reasonable amount of time. Position i of the output can be taken by any character in the input up to position 10i, this complies with the challenge requiring at least a range from i-9 to i+9. # C, 214 bytes c;i;char B[19]={0};char*I; S(p,q){if(B[p]-B[q])B[p]^=(B[q]^=(B[p]^=B[q]));} R(n){while(n--)putchar(B[c]),B[c]=*I,c=++i%19,I++;} main(c,v)char**v;{srand(time(0));I=v[1];R(19);i=9;for(;;){S(i,rand()%19);R(1);i=++i%19;}}  How it works Try Online (UNIX) #include <stdio.h> #include <unistd.h> // animation speed #define ANIMATION_SLOW 600000 #define ANIMATION_NORMAL 400000 #define ANIMATION_FAST 200000 c;i;char Buffer[19]={0};char*input; Swap(p,q){if(Buffer[p]!=Buffer[q])Buffer[p]^=(Buffer[q]^=(Buffer[p]^=Buffer[q]));} Read(n){while(n-->0)putchar(Buffer[c]),Buffer[c]=*input,c=++i%19,input++;} main(int argc, char**argv) { // initialization srand(time(0)); input=argv[1]; Read(19);i=9; // shuffle machine while(1) { usleep(ANIMATION_NORMAL); Swap(i,rand()%19); Read(1); i=++i%19; } }  • What does the "swap" in your diagram mean? May 14, 2017 at 19:36 • @MartinEnder it means that Vi is swapped with Vj where j = RAND [ i-9, i+9 ] to satisfy the question criteria 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 May 14, 2017 at 20:19 • Ah that makes sense, thanks. May 14, 2017 at 20:47 • Can I ask what tool you used to create your diagram? – Dada May 15, 2017 at 8:41 • @Dada Gliffy May 15, 2017 at 11:00 # 05AB1E, 13 bytes [I)˜¼¾T›i.rć,  Try it online! (modified to take 20 elements) [ # Infinite loop I)˜ # Add the next element from input to the array ¼ # Increment the counter variable ¾T›i # If the counter variable is greater than 10... .r # Get a random permutation of the array ć, # Print and remove the first element  # Bash, 17 bytes xargs -n9 shuf -e  Try it online! xargs continuously takes 9 letters from STDIN and sends them to shuffle an infinite list can be generated by: yes {a..z}  which prints a b c d e .. z infinite times. Test could be done by: yes {a..z} | xargs -n9 shuf -e  • not sure if xargs shuf -e satisfies the requirements May 15, 2017 at 15:16 # R, 70 bytes x=NULL;repeat{x=sample(c(x,scan()));if(sum(x|1)>9){cat(x[1]);x=x[-1]}}  Starts with an empty vector x. In an infinite loop, it takes a new value from STDIN, then shuffles the vector. Then it checks if the length of the built up list is 10 or higher. If it is, it can start printing. This way the vector has a buffer of 10 inputs, each getting shuffled in every iteration. So it is possible for input to be printed 10 places earlier, and infinitely many places later (following a geometric distribution with p=1/10). When the buffer is long enough, the first element is printed and removed from the vector. # Javascript, 78 bytes for(l=[];;){l.push(prompt());l.length==10&&alert(l.splice(Math.random()*9,1))};x.sort(()=>Math.random()<0.5);alert(x)}  Uses the same method as xnor's answer. # Perl 5, 39 bytes 38 bytes of code + -n flag. print splice@F,rand 10,1if 9<push@F,$_


Try it online!

Add each element to @F array (with push@F,$_). When @F contains 10 elements (push returns the number of elements in the array, hence 9<push...), a random element is removed and printed (splice@F,rand 10,1 to remove the element, print to print it). The output starts happening after then 10th element has been read. Hence, each element can start appearing at least 9 positions before its original one, and can be shifted to the right infinitely. # SmileBASIC, 61 58 bytes @L B$=B$+R()IF I>8THEN R=RND(9)?B$[R];:B\$[R]="
I=I+1GOTO@L


Each character of the infinite list is added to the end of the buffer. When the buffer length is 11, a random character is printed and removed.

Function R generates the next character.

# Prolog, 70 bytes

s(L):-get0(C),(length(L,9)->random_select(H,L,R),put(H);L=R),s([C|R]).

• Sorry, I didn't say how to call it: s([]). E.g. with an empty list. May 14, 2017 at 17:53
• Welcome to PPCG! Could you explain how this works? I'm not sure what you mean by "e.g. with an empty list". Solutions should work (and only need to work) with infinite lists. May 14, 2017 at 19:37