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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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

b=1
lbla
x=15+b*15
b=1
lblb
readIO
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

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 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;
    }
}

Answer 10

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 

Answer 11

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 

Answer 12

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.

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

Prolog, 70 bytes

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