Infinite Sequence of Unique Random Integers

Question

Output an infinite sequence of positive integers, such that, for each element in the sequence, all positive integers that have not yet been output have a positive probability of being chosen, and no value is repeated.

For example, if the first integer is 3, then 3 may not be output again, but all other positive integers have a positive probability of being chosen for the second integer.

Acceptable output methods

• Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program
• A named or unnamed function which returns an infinite iterable (such as a Python generator)
• A named or unnamed function which outputs the sequence one integer at a time each time it is called within a single execution of the program
• A named or unnamed function or program which outputs the next integer in the sequence when called with the previous integer(s) as its sole argument(s) (the first call may either take no arguments or take a seed argument, which may be included in the arguments to later calls)

Rules

• There will be no input except an optional seed value, which will be an infinite sequence of random bits.
• Submissions must be capable of producing different outputs given different initial conditions (outputting the same sequence every time is not acceptable).
• Each element of the sequence must be chosen randomly out of the valid elements (positive integers not already present in the sequence).
• You may assume that you have infinite memory available.
• You may assume that any real numbers returned by a PRNG are infinite-precision. In other words, if you have a function called rand that returns a random value in [0, 1), you may assume every real value in that interval has a positive probability of being chosen, rather than just the subset of the reals that are representable with floats.
• Each integer must be output in a finite amount of time after the last integer (so you can't wait until program termination to output part of the sequence). The first integer must be output in a finite amount of time after the program is started or the function is called.

Answer 1

Python 3, 137 127 123 138 117 99 98 bytes

A named or unnamed function which returns an infinite iterable (such as a Python generator)

from random import*
def f(x=[],y=1):
 while y in x or.5<random():y+=1
 yield y;yield from f(x+[y])

• -10 bytes by putting the conditional in one line (Thanks, @Dennis)
• -4 bytes by initializing r at the beginning of the loop
• +15 bytes by remembering numbers can contain zeroes...
• -21 bytes by renaming randint, and moving the condition in the head of the inner loop
• -18 bytes by switching to a functional paradigm
• -1 bytes by moving from or ...>.5 to .5<random() (thanks, @JonathanAllan)

Answer 2

MATL, 10 bytes

`x1r/XktGm

Try it online!

Explanation

A candidate output, say n, is generated as ceil(1/r), where r is uniformly distributed on the interval (0,1). This ensures that every positive integer has a positive probability of being chosen as n (assuming infinite precision for r).

If n coincides with any of the previous numbers (taken as input) the process is repeated.

`       % Do...while
  x     %   Delete. This deletes the candidate number from the preceding iteration.
        %   In the first iteration it takes input implicitly and deletes it.
  1     %   Push 1
  r     %   Push random number uniformly distributed on (0,1)
  /     %   Divide
  Xk    %   Round up (ceil). This is the candidate output. It will only be valid
        %   if it's not present in the input
  t     %   Duplicate
  G     %   Push input: forbidden numbers
  m     %   Ismember. This will be used as loop condition
        % End (implicit). If condition is true, next iteration
        % Display (implicit)

Answer 3

Python 2, 93 87 bytes

-3 bytes thanks to Uriel (move r=1 to beginning of the loop to avoid initialisation)

from random import*
a=[]
while 1:
 r=1
 while r in a or.5<random():r+=1
 a+=[r];print r

Try it online!

Keeps adding one while the number is either unavailable or a coin flip comes up heads.
Low numbers have much more probabilistic weight than high numbers.

Answer 4

JavaScript, 62 bytes

A full program that picks a single random value in [0 .. 1] and expressed it as a continued fraction, omitting elements that have been encountered before. This would produce a really infinite sequence if the initial value had an infinite precision. In practice, we are limited to what can be expressed in IEEE-854 format.

for(x=Math.random(),o=[];;)o[n=1/x|0,x=1/x-n,n]||alert(o[n]=n)

Demo

Here is a demo limited to 50 values and writing to the console instead.

for(x=Math.random(),o=[],i=0;i<50;)o[n=1/x|0,x=1/x-n,n]||console.log(o[i++,n]=n)

Answer 5

Aceto, 29 21 bytes

Writing to STDOUT, with a consistent, unambiguous separator between integers (such as a newline), with output prior to termination of the program

p<LL
 v`O
I?<\
0MLCnO

1. Push a zero, increment it and go in a random direction. Two of the directions lead back to the random direction field, one leads back to incrementation (so it is incremented a random amount of times).
2. When the fourth choice is made, we memorize and immediately load the value, then check whether it's contained in the stack already. If so, we jump to the origin and try again.
3. Otherwise, we load the value twice (once for printing, once for storage), print it and a newline and go back to the origin.

Massively favours low numbers, but there is a small chance for it to print any number at any point.

Answer 6

Bash, 23 bytes

yes \ |nl|xargs shuf -e

Try it online!

yes \ prints infinite spaces, nl numbers lines, suff -e shuffless lines without repetition.

Answer 7

Python 2, 39 bytes

f=lambda l,s:sum({1/s//1}-l)or f(l,s/2)

Try it online!

Takes a list l of previous outputs (as a set) and a seed s that's a random real from 0 to 1.

Answer 8

Japt, 17 bytes

aA=(1/Mr)c)<0?A:ß

Try it online!

Answer 9

Java 8, 136 bytes

import java.util.*;()->{Set s=new HashSet();for(int n;;s.add(n))System.out.print(!s.contains(n=new Random().nextInt(-1>>>1))?n+";":"");}

Explanation:

Try it here. (Wait 60 seconds for the TIO to time-out to see the result.)

import java.util.*;     // Required import for the Set, HashSet, and Random

()->{                   // Method without parameters nor return-type
  Set s=new HashSet();  //  Set to keep track of numbers we've already outputted
 for(int n;;            //  Loop infinitely
     s.add(n))          //   And every time we output a random number, add it to the Set
   System.out.print(    //   Output:
    !s.contains(        //    If we haven't outputted it yet:
     n=new Random().nextInt(-1>>>1))?n+";"
                        //     A random number (range of int: 0 - 2³²)
    :                   //    Else:
     "");               //     Output nothing
}                       // End of method

Answer 10

Haskell, 60 59 56 bytes

((a:b)#h)(n:r)|n=a:((h++b)#[])r|q<-a:h=(b#q)r
[1..]#[]

Takes the seed as an infinite list of Bool.

Usage example: ([1..]#[]) [True,False,False,True,True,False,True,True,False,True,False,True,True,False,False,False,False,False,False,True....] -> [1,4,3,5,2,7,8,6,15,...].

Try it online!

Start with the list [1..]. If the next element from the seed is False, skip the next element of the list. If it's a True, output the current element, remove it from the list and start from the beginning. h keeps track of the skipped elements and is prepended (-> h++b) to the list of available numbers in the True case.

Answer 11

Clojure, 112 (or 119) 114 bytes

Update, uses 1 / (rand) to get an "infinite" range of bigints:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0#{}](for[i(range)](bigint(/(rand)))))))

Original:

#(filter pos?(map first(reductions(fn[[v p]r](if(p r)[0 p][r(conj p r)]))[0 #{}](for[i(range)](rand-int 2e9)))))

I'm hoping to see an alternative approach. Anyway, this will generate integers between 1 and 2e9, Java's integers are signed to the "real" maximum is 2147483647, which is 7 bytes longer expression (Integer/MAX_VALUE is even longer). 0 is used as an indication of a duplicate values and are filtered from the output sequence.

Answer 12

Clojure, 100 bytes

(fn[](let[a(atom[])](filter #(if-not(some #{%}@a)(swap! a conj %))(repeatedly #(bigint(/(rand)))))))

This function returns an infinite sequence of integers. To get the nth number of this series:

(nth (fn[]...) n)

To get the first n terms of this series:

(take n (fn[]...))

EDIT: Golfed 11 bytes (Thanks @NikoNyrh!) and added 3 bytes (changed int to bigint, to improve accuracy).

Answer 13

JavaScript ES6, repeating call, 50 Bytes

c={0:9};f=_=>c[~~_]|Math.random()<.9?f(-~_):c[_]=_

Answer 14

JavaScript REPL, 48 bytes

for(o=[];;)o[n=1/Math.random()|0]||alert(o[n]=n)

Answer 15

APL, 33 bytes

∇P
S←⍬
→2/⍨S∊⍨X←⌊÷1-?0
S,←⎕←X
→2∇

Answer 16

Mathematica, 83 bytes

s=5;l={};t=1;While[t<30,If[l~FreeQ~s,Print@s];l~AppendTo~s;s=RandomInteger@100;t++]

starting with 5

Try it online!