40

This works almost fine but the number starts with 0 sometimes:

import random
numbers = random.sample(range(10), 4)
print(''.join(map(str, numbers)))

I've found a lot of examples but none of them guarantee that the sequence won't start with 0.

10
  • 3
    You can specify in range() the start value.In your case it could be 1
    – kuro
    Apr 24, 2017 at 16:27
  • 33
    This works almost fine but the number starts with 0 sometimes. Probably about 10% of the time, if you run it enough times.
    – WBT
    Apr 24, 2017 at 19:34
  • 5
    Related PPCG challenge
    – mbomb007
    Apr 24, 2017 at 21:48
  • 2
    A security related Q&A: When choosing a numeric PIN, does it help or hurt to make each digit unique?
    – HamZa
    Apr 25, 2017 at 14:58
  • 1
    To the OP: Please retract your acceptance of your accepted answer. It should not be the accepted answer. It is the slowest of the top six answers, and by quite a wide margin. Apr 25, 2017 at 20:57

12 Answers 12

70

We generate the first digit in the 1 - 9 range, then take the next 3 from the remaining digits:

import random

# We create a set of digits: {0, 1, .... 9}
digits = set(range(10))
# We generate a random integer, 1 <= first <= 9
first = random.randint(1, 9)
# We remove it from our set, then take a sample of
# 3 distinct elements from the remaining values
last_3 = random.sample(digits - {first}, 3)
print(str(first) + ''.join(map(str, last_3)))

The generated numbers are equiprobable, and we get a valid number in one step.

7
  • 12
    @Claudio Independence of the numbers generated is one of the fundamental properties a good pseudo-random generator must satisfy. I suppose that Python's random is good enough that subsequent calls can be considered independent. Apr 24, 2017 at 18:22
  • 2
    Note that, while this method does indeed generate each possible output with the same probability, this fact isn't trivially obvious. The key reason why it does produce equiprobable reasons is that, after picking the first digit, the number of remaining possible digits is the same regardless of which first digit was chosen. In particular, if you tried to reverse the procedure (i.e. first pick the lowest three distinct digits, and then pick a non-zero first digit out of the remaining seven), the outputs would not be equiprobable. (Exercise to readers: why?) Apr 25, 2017 at 16:12
  • 3
    Downvoted because this is the slowest of the top answers. This combines set arithmetic with random.sample, both of which are slow. Apr 25, 2017 at 18:01
  • 1
    @DavidHammen Why is that worthy of a downvote? On my machine, this answer is less than 4 microseconds slower than Austin Hastings answer, and performance wasn't even mentioned in the question. I would hesitate to call a constructive approach alongside rejection sampling techniques "not useful".
    – miradulo
    Apr 26, 2017 at 13:47
  • @Mitch - Mostly to counter what I consider to be completely invalid downvotes on the other answers due to lack of understanding of the concept of rejection sampling. An easy way to understand rejection sampling: Suppose I asked you to produce all of the four digit numbers that have no repeated digits and that start with 1. You could come up with a complex algorithm to do that, or you could use [n for n in range(1000,10000) if len(set(str(n)))==4]. (continued) Apr 26, 2017 at 14:19
33

Just loop until you have something you like:

import random

numbers = [0]
while numbers[0] == 0:
    numbers = random.sample(range(10), 4)

print(''.join(map(str, numbers)))
7
  • 7
    @Claudio the probabilities still work out to be equal for all results so I'm not sure what you mean by not as random as it should be
    – muddyfish
    Apr 24, 2017 at 18:38
  • 6
    @Claudio I'm sorry but you should probably consult some kind of reference on accept-reject sampling and review conditional probability before suggesting all of the answers are incorrect.
    – miradulo
    Apr 24, 2017 at 18:39
  • 1
    This could loop forever. Hardly a versatile solution. Apr 25, 2017 at 15:09
  • 12
    @BoundaryImposition, and all the other downvoters: This is a very versatile solution. It even has a name, "rejection sampling." Most implementations of a normal distribution use rejection sampling. Apr 25, 2017 at 16:24
  • 3
    @BoundaryImposition, and all the other downvoters: Of the answers by Austin Hastings, MSeifert, karakfa, andThierry Lathuille, this is the fastest in both python 2.7 and python 3.4. In fact, the accepted answer is the slowest, 40% slower than is this answer (python 2.7). Apr 25, 2017 at 17:21
20

This is very similar to the other answers but instead of sample or shuffle you could draw a random integer in the range 1000-9999 until you get one that contains only unique digits:

import random

val = 0  # initial value - so the while loop is entered.
while len(set(str(val))) != 4:  # check if it's duplicate free
    val = random.randint(1000, 9999)

print(val)

As @Claudio pointed out in the comments the range actually only needs to be 1023 - 9876 because the values outside that range contain duplicate digits.

Generally random.randint will be much faster than random.shuffle or random.choice so even if it's more likely one needs to draw multiple times (as pointed out by @karakfa) it's up to 3 times faster than any shuffle, choice approach that also needs to join the single digits.

20
  • 2
    @MSeifert Of course, that's for 4 digits. Your rejection space is going to blow up and slow you down with say, 7 digits (I know that's not the question :) ). Practically speaking though, I like this answer best.
    – miradulo
    Apr 24, 2017 at 17:50
  • 7
    To make it even more perfect you can limit further the range for choices using for example random.randint(1023, 9876), right?
    – Claudio
    Apr 24, 2017 at 18:58
  • 1
    @DavidHammen Note that with python-3 the timings look very different: ideone.com/ous7zZ. Am I right that it seems my solution is a bit slower on python2 but much faster in python3?
    – MSeifert
    Apr 25, 2017 at 20:57
  • 1
    @MSeifert - I didn't notice the python3 tag. I have experimented with both python2 and python3 and have noticed that performance is in general quite abysmal with python3. Your's is the one exception, being only 10% slower in python3 rather than python2 (other algorithms take twice as long, or longer). One thing that is common across both versions of the language is that the accepted answer is lousy. Apr 25, 2017 at 21:02
  • 1
    @MSeifert -- Even your algorithm is a bit slower in python3 than it is in python2. I reduced the timeit number on ideone so as not to overly abuse their computers. Expand that number and it's clear than every algorithm is slower in python3. I suspect that python3 has drastically improved the performance of len, set, and str, but has somehow disimproved the performance of random, with particular attention paid to disimproving the performance of random.sample and random.shuffle. Apr 25, 2017 at 21:11
16

I do not know Python well, but something like

digits=[1,2,3,4,5,6,7,8,9] <- no zero
random.shuffle(digits)
first=digits[0] <- first digit, obviously will not be zero
digits[0]=0 <- used digit can not occur again, zero can
random.shuffle(digits)
lastthree=digits[0:3] <- last three digits, no repeats, can contain zero, thanks @Dubu

A more useful iteration, actually creating a number:

digits=[1,2,3,4,5,6,7,8,9]   # no zero
random.shuffle(digits)
val=digits[0]                # value so far, not zero for sure
digits[0]=0                  # used digit can not occur again, zero becomes a valid pick
random.shuffle(digits)
for i in range(0,3):
  val=val*10+digits[i]       # update value with further digits
print(val)

After stealing pieces from other solutions, plus applying the tip from @DavidHammen:

val=random.randint(1,9)
digits=[1,2,3,4,5,6,7,8,9]
digits[val-1]=0
for i in random.sample(digits,3):
  val=val*10+i
print(val)
8
  • 1
    I don't know why this was downvoted, it's short and combinatorical. It's exactly how I thought of doing it when reading the title. Setting first to 0 after getting first digit is "clever", I would have just added zero back to the list. This looks to be identical to Claudio's, which is tl;dr and less readable. This can generate all 4536 answers, without unnecessary looping or testing. Apr 25, 2017 at 4:27
  • This is good, except that it should read lastthree=digits[0:3] because of Python's unusual array indexing.
    – Dubu
    Apr 25, 2017 at 8:24
  • @toddkaufmann I wanted to do that first, just I did not know the syntax for appending an item, and then I realized it was not needed anyway
    – tevemadar
    Apr 25, 2017 at 8:38
  • @tevemadar -- While correct, this is quite slow, with two calls to random.shuffle on a nine element list. Apr 25, 2017 at 19:12
  • @DavidHammen I was not aware of other random functions, like random.sample (despite of using almost identical variable names, I have not spotted the later-accepted answer, there were much-much more failed answer attempts around). Adding a 3rd variant, by the way
    – tevemadar
    Apr 25, 2017 at 20:31
11

[Fixed] Shift all four digits on one position is not right. Swap leading zero with fixed position is not right too. But random swap of the leading zero with any of nine positions is correct and gives equal probability:

""" Solution: randomly shuffle all numbers. If 0 is on the 0th position,
              randomly swap it with any of nine positions in the list.

  Proof
    Lets count probability for 0 to be in position 7. It is equal to probability 1/10 
  after shuffle, plus probability to be randomly swapped in the 7th position if
  0 come to be on the 0th position: (1/10 * 1/9). In total: (1/10 + 1/10 * 1/9).
    Lets count probability for 3 to be in position 7. It is equal to probability 1/10
  after shuffle, minus probability to be randomly swapped in the 0th position (1/9)
  if 0 come to be on the 0th position (1/10) and if 3 come to be on the 7th position
  when 0 is on the 0th position (1/9). In total: (1/10 - 1/9 * 1/10 * 1/9).
    Total probability of all numbers [0-9] in position 7 is:
  9 * (1/10 - 1/9 * 1/10 * 1/9) + (1/10 + 1/10 * 1/9) = 1
    Continue to prove in the same way that total probability is equal to
  1 for all other positions.
    End of proof. """

import random
l = [0,1,2,3,4,5,6,7,8,9]
random.shuffle(l)
if l[0] == 0:
    pos = random.choice(range(1, len(l)))
    l[0], l[pos] = l[pos], l[0]
print(''.join(map(str, l[0:4])))
10
  • 3
    But the not every possible value is drawn with the same probability. Because for example 1234 and 01234 produce the same result while numbers containing a not-leading zero (e.g. 1023) have only one possibility to be drawn.
    – MSeifert
    Apr 24, 2017 at 19:35
  • @MSeifert Ahh you're correct.. How about swapping zero with a random location in the list should a zero-leading number be drawn? Then we redistribute evenly back across the sample space in that case.
    – miradulo
    Apr 24, 2017 at 19:50
  • e.g. random.shuffle(l); if l[0] == 0: pos = random.choice(range(1, 10)); l[0], l[pos] = l[pos], l[0]
    – miradulo
    Apr 24, 2017 at 19:56
  • 1
    @MSeifert -- Lets take simpler example: list [0,1,2] and two unique digits not starting with 0. There are 3!==6 possibilities. Each possibility has probability 1/6. There are 2 leading zeros: [0,1,2] and [0,2,1]. If randomly swap leading 0 with the rest 2 positions, there are four combinations: [0,1,2]==>([1,0,2] and [2,1,0]); [0,2,1]==>([2,0,1] and [1,2,0]). Each of these four combinations have the same probability equal to 1/6 * 1/2 == 1/12. But these 4 combinations coincide with the rest 4 possibilities. So each possibility after random swap should have probability == 1/6 + 1/12.
    – FooBar167
    Apr 24, 2017 at 21:32
  • 1
    @MSeifert -- added mathematical proof.
    – FooBar167
    Apr 25, 2017 at 11:41
11

rejection sampling method. Create a 4 digit random combination from 10 digits and resample if it doesn't match the criteria.

r4=0    
while r4 < 1000:
    r4=int(''.join(map(str,random.sample(range(10),4))))

noticed that this is essentially the same as @Austin Haskings's answer

7
  • 3
    Probability of that is zero... You'll be surprised how common this technique is used in practice.
    – karakfa
    Apr 25, 2017 at 15:14
  • 2
    The probability is certainly not zero. Apr 25, 2017 at 15:22
  • 1
    lim 10^(-n) = 0; for n -> Infinity (aka forever)
    – karakfa
    Apr 25, 2017 at 15:32
  • 2
    The probability is negligible for all practical purposes. For example, to loop 1000 times without producing a valid sample (which takes 16 msecs on my computer) is probability 10^(-1000) event.
    – karakfa
    Apr 25, 2017 at 16:16
  • 7
    @BoundaryImposition - You are barking up the wrong tree here. Rejection sampling is a very widely used technique. The only problems with this answer is that Austin Hasking's wrote a very similar answer two minutes earlier (probably while karakfa was writing this answer) and that Austin Hasking's answer is a bit better. Apr 25, 2017 at 16:34
7

You could use full range for 3 numbers, then choose the leading number among the remaining numbers:

import random
numbers = random.sample(range(0,10), 3)
first_number = random.choice(list(set(range(1,10))-set(numbers)))
print(''.join(map(str, [first_number]+numbers)))

Another way if the choice needs to be repeated (and if you remain reasonable on the number of digits), is to pre-compute the list of the possible outputs using itertools.permutations, filtering out the ones with a leading zero, and building a list of integers from it:

import itertools,random

l = [int(''.join(map(str,x))) for x in itertools.permutations(range(10),4) if x[0]]

That's some computation time, but after than you can call:

random.choice(l)

as many times you want. It's very fast and provides an evenly distributed random.

4
  • 10
    Except the allowable outcomes aren't equally likely then; e.g., there are two ways to get 1230, but only one way to get 1234.
    – Tim Peters
    Apr 24, 2017 at 16:36
  • @TimPeters you're right. Added an alternate solution. Apr 24, 2017 at 16:40
  • if you get 0023, then you have the same problem
    – janscas
    Apr 24, 2017 at 16:41
  • 4
    but you cannot have 0023. There's only one 0 Apr 24, 2017 at 17:05
4

I don't know Python so I will post a pseudo-code-ish solution for this specific problem:

  • Create a lookup variable containing a 0-based list of digits:

    lu = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
  • Generate four 0-based random numbers as follows:

    r1 = random number between 0 and 8
    r2 = random number between 0 and 8
    r3 = random number between 0 and 7
    r4 = random number between 0 and 6
    
  • Use the lookup variable to convert random numbers to digits one-by-one. After each lookup, mutate the lookup variable by removing the digit that has been used:

    d1 = lu[r1]
    lu.remove(d1)
    lu.insert(0)
    
    d2 = lu[r2]
    lu.remove(d2)
    
    d3 = lu[r3]
    lu.remove(d3)
    
    d4 = lu[r4]
    lu.remove(d4)
    
  • Print the result:

    print concatenate(d1, d2, d3, d4)
    

It is possible to generalize this idea a little. For example you can create a function that accepts a list (of digits) and a number (desired length of result); the function will return the number and mutate the list by removing used-up digits. Below is a JavaScript implementation of this solution:

function randomCombination(list, length) {
    var i, rand, result = "";
    for (i = 0; i < length; i++) {
        rand = Math.floor(Math.random() * list.length);
        result += list[rand];
        list.splice(rand, 1);
    }
    return result;
}

function desiredNumber() {
    var list = [1, 2, 3, 4, 5, 6, 7, 8, 9],
        result;
    result = randomCombination(list, 1);
    list.push(0);
    result += randomCombination(list, 3);
    return result;
}

var i;
for (i = 0; i < 10; i++) {
    console.log(desiredNumber());
}

2

Here's how I'd do it

while True:
    n = random.randrange(1000, 10000)
    if len(set(str(n))) == 4: # unique digits
        return n

More generally, given a generator, you can use the built-ins filter and next to take the first element that satisfies some test function.

numbers = iter(lambda: random.randrange(1000, 10000), None) # infinite generator
test = lambda n: len(set(str(n))) == 4
return next(filter(test, numbers))
1
  • 1
    return outside a function is a syntaxerror in python. Also note that you can use a range from 1023 to 9876 as pointed out here.
    – MSeifert
    Apr 25, 2017 at 14:47
1

Combine generators with next

A Pythonic way to write would be to use 2 nested generators and next:

from random import randint
from itertools import count

print(next(i for i in (randint(1023, 9876) for _ in count()) if len(set(str(i))) == 4))
# 8756

It's basically a one-liner variant of @MSeifert's answer

Preprocess all the acceptable numbers

If you need many random numbers, you could invest some time and memory for preprocessing all the acceptable numbers:

import random    
possible_numbers = [i for i in range(1023, 9877) if len(set(str(i))) == 4]

1023 and 9877 are used as boundaries because no int lower than 1023 or greater than 9876 can have 4 unique, distince numbers.

Then, you'd just need random.choice for a very fast generation:

print(random.choice(possible_numbers))
# 7234
1

Disclaimer: this is a terrible anti-Python approach, strictly for the benchmarking part (see @DavidHammen's comments around, and http://ideone.com/qyopLF) The idea is to generate the sequence numbers of the digits in one step, and then fix any collisions:

rnd=random.randint(0,4535)
(rnd,d1)=divmod(rnd,9)
(rnd,d2)=divmod(rnd,9)
#(rnd,d3)=divmod(rnd,8)
#(rnd,d4)=divmod(rnd,7)
(d4,d3)=divmod(rnd,8) # miracle found: 1 divmod happens to run faster than 2

Now we have d1=0..8, d2=0..8, d3=0..7, d4=0..6, it can be tested via running the snippet with rnd=4535 (4535=9*9*8*7-1, by the way)

First, d1 has to be patched up

d1=d1+1 # now d1 = 1..9

Then d2 has to "skip" d1 if necessary

if d2>=d1
  d2=d2+1 # now d2 = 0..9 "-" d1

Then the same has to be done with the remaining digits, getting ugly fast:

if d3>=d1:
  d3=d3+1    # now d3 = 0..8 "-" d1
  if d3>=d2:
    d3=d3+1  # now d3 = 0..9 "-" {d1,d2}
elif d3>=d2: # this branch prepares for the other variant
  d3=d3+1
  if d3>=d1: # ">=" is preserved for consistency, here "==" may occur only
    d3=d3+1

And the final part is the catastrophic one:

if d4>=d1:
  d4=d4+1
  if d4>=d2:
    d4=d4+1
    if d4>=d3:
      d4=d4+1
  elif d4>=d3:
    d4=d4+1
    if d4>=d2:
      d4=d4+1
elif d4>=d2:
  d4=d4+1
  if d4>=d1:
    d4=d4+1
    if d4>=d3:
      d4=d4+1
  elif d4>=d3:
    d4=d4+1
    if d4>=d1:
      d4=d4+1
elif d4>=d3:
  d4=d4+1
  if d4>=d2:
    d4=d4+1
    if d4>=d1:
      d4=d4+1
  elif d4>=d1:
    d4=d4+1
    if d4>=d2:
      d4=d4+1

For longer numbers, it might work faster with bitfields, but I do not see a trivial way. (Checking the >= relations once is not enough, because the collision can easily occur after doing an incrementation. e.g. d1=1, d2=2, d3=1: d3 collides with d1, but it does not collide with d2 initially. However after "puching the hole" at 1, d3 becomes 2 and now it collides with d2. There is no trivial way to spot this collision in advance)

As the code stinks as hell, I put a verification step at the end

val = d1*1000 + d2*100 + d3*10 + d4
#if len(set(str(val))) != 4: print(str(val)+" "+str(o1)+","+str(o2)+","+str(o3)+","+str(o4))
if len(set(str(val))) != 4: print(val)

It is already faster than the other really fast code (the commented verification displayed the original digits preserved after the divmod-s, for debugging purposes. This is not the kind of code which works immediately...). Commenting both verifications makes it even faster.

EDIT: about checking this and that

This is an approach maintaining an 1:1 relation between the minimal set of valid inputs (0...4535) and valid outputs (the 9*9*8*7 possible 4-digit numbers with distinct digits, not-starting-with-0). So a simple loop can and should generate all the numbers, they can be checked one-by-one and they can be collected into a set for example in order to see if they are all distinct results

Practically:

collect=set()
for rnd in range(0,4536):
    (rnd,d1)=divmod(rnd,9)
    ... rest of the code, also the verification step kept active ...
    collect.add(val)
print(len(collect))

1) It will not print anything in the loop (all results are 4-digit numbers with distinct digits)

2) It will print 4536 at the end (all results are distinct)

One can add a verification for the first digit (d1), here and now I just assume that
"(something mod 9)+1" will not be 0.

2
  • Interesting. Did you check that the results are uniformly distributed? Apr 27, 2017 at 8:54
  • @EricDuminil the distribution over the set of valid outputs follows the distribution of randint(). What I checked is the correctness of mapping inputs to outputs, added some lines about it now
    – tevemadar
    Apr 27, 2017 at 9:56
-6

This will allow zeros after the first digit -

numbers = random.sample(range(1,10),1) + random.sample(range(10),3)
2
  • 4
    It will also allow a single repeated digit. Apr 24, 2017 at 16:33
  • Would you need to multiply the first digit by 1000 before adding the two? Or does the plus sign just concatenate them?
    – Dima
    Apr 24, 2017 at 16:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.