Infinite Sequence of Unique Random Integers

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.
• So, shouldn't the first number (and all the following ones) have an infinite number of digits? – Arnauld May 21 '17 at 21:07
• @Arnauld Integers are finite. You're outputting an infinite number of integers, not integers with infinite length (which don't exist). – Mego May 21 '17 at 21:09
• @LuisMendo I'm not sure what you're asking. – Mego May 21 '17 at 21:10
• What I mean is that if the sequence really is infinite (which of course is not going to be the case in practical implementations), the number of digits of the numbers tends to infinity. And if each element of the sequence is chosen randomly out of the valid elements, I don't see why the first numbers of the sequence should be small ones. But I may be missing something. – Arnauld May 21 '17 at 21:29
• @Arnauld There is no requirement that all valid integers have equal probability (in fact, there can't be, because then that probability would be infinitesimal). It's perfectly valid to have the probability of an integer n being chosen be 1/n, which would cause smaller values to have much larger probabilities than larger values. – Mego May 21 '17 at 21:30

Python 3, 13712712313811799 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)
• The entire if statement can go on a single line. – Dennis May 21 '17 at 21:00
• @Mego Just switched to Python 3, I'm sure I can save characters elsewhere. – L3viathan May 21 '17 at 21:00
• @JonathanAllan I guess I did... It wasn't intentional, it happened while I made it a generator after having read your answer... My Aceto answer is then also inspired by your answer. – L3viathan May 21 '17 at 22:17
• That is a lot of golfing. nj – Rɪᴋᴇʀ May 21 '17 at 22:41

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)

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.

• you can cut 3 bytes by moving the r=1 to the beginning of the loop and deleting the third line – Uriel May 22 '17 at 18:22

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.

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)

• Would this output a single value in finite time in the imagined scenario where we have infinite precision? – Jonathan Allan May 21 '17 at 22:03
• @JonathanAllan Actually, I think so. A random real r with infinite precision must be an irrational number that maps to an infinite sequence of random integers An such that r = A0+1/(A1+1/(A2+1/...)), so any 'new' value of An can be picked in finite time. – Arnauld May 21 '17 at 22:16
• That seems like you are suggesting that 0.5 is not a real number :/ – Jonathan Allan May 21 '17 at 22:17
• The infinite precision really is important here. It assumes that the PRNG can support infinite precision and can't possibly generate exactly 0.5. Does that make sense? (It's more like 0. followed by an infinite number of random digits.) – Arnauld May 21 '17 at 22:20
• Yeah I think the premise of infinite precision makes the question impossible to specify clearly to be honest. If 0.5 has zero chance of being output then so does every other real number too. – Jonathan Allan May 21 '17 at 22:25

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.

Bash, 23 bytes

yes \ |nl|xargs shuf -e

Try it online!

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

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.

• The seed should be an integer. – Jonathan Allan May 21 '17 at 21:25
• @JonathanAllan I thought Mego OK'ed an infinite precision real in the comments. I'll confirm. – xnor May 21 '17 at 21:26
• ...also I think l should be defaulted to an empty container of some description. – Jonathan Allan May 21 '17 at 21:26
• If they did it's a game changer. – Jonathan Allan May 21 '17 at 21:26
• @JonathanAllan Reals are OK. I'm using the option that takes the previous integers as input. – xnor May 21 '17 at 21:42

Japt, 17 bytes

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

Try it online!

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

Haskell, 6059 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,...].

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.

• What if the infinite list contains only 0's? – Qwerp-Derp May 26 '17 at 10:16
• @Qwerp-Derp: then there's no output. Some of the other answers run into the same problem if the random function returns the same number over and over again. I'm just using the seed itself as the random sequence. – nimi May 26 '17 at 10:38

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.

• You can save a byte by using (repeatedly #(rand-int 2e9)) instead of (for[i(range)](rand-int 2e9)). – madstap May 23 '17 at 5:50
• Whoops, I overlooked the fact that you're already inside a function literal; can't nest those... – madstap May 23 '17 at 6:03
• I made an alternative approach! I'm not sure what the range is for the numbers supported, though... – Qwerp-Derp May 26 '17 at 10:15
• This is not valid. Only outputting integers between 1 and 2e9 generates a finite sequence. – Mego May 27 '17 at 5:43

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

• Nice option to hold the state, I got this approach down to 98 bytes by using if-not (dropping explicit false and true) and using unary version of /: #(int(/(rand))). Not sure if bigint would be more correct here as the result of that division might overflow int. – NikoNyrh May 28 '17 at 13:39

JavaScript ES6, repeating call, 50 Bytes

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