How do I make a list of random unique tuples?

user_5356096 0
Viewed 1433

I've looked over several answers similar to this question, and all seem to have good oneliner answers that however only deal with the fact of making the list unique by removing duplicates. I need the list to have exactly 5.

The only code I could come up with is as such:

from random import *

tuples = []

while len(tuples) < 5:
    rand = (randint(0, 6), randint(0,6))
    if rand not in tuples:
        tuples.append(rand)

I feel like there is a simpler way but I can't figure it out. I tried playing with sample() from random:

sample((randint(0,6), randint(0,6)), 5)

But this gives me a "Sample larger than population or is negative" error.

tuples unique python-3.x random python
2 Answers

One quick way is to use itertools.product to generate all tuple possibilities before using sample to choose 5 from them:

from itertools import product
from random import sample
sample(list(product(range(7), repeat=2)), k=5)
user_68909120

For such a small set of inputs, just generate all possible outputs, and sample them:

 import itertools
 import random

 size = 6
 random.sample(list(itertools.product(range(size+1), repeat=2)), 5)

You indicate that the bounds (size) may be a parameter though, and if the bounds might be even a little larger, this could be a problem (you'd be generating size ** 2 tuples to select 5 of them, and the memory usage could get out of control). If that's a problem, given you only need a pair of integers, there is a cheap trick: Choose one random integer that encodes both resulting integers, then decode it. For example:

size = 6
raw_sample = random.sample(range((size + 1) ** 2), 5)
decoded_sample = [divmod(x, size+1) for x in raw_sample)]

Since range is zero overhead (the memory usage doesn't depend on the length), you can select precisely five values from it with overhead proportionate to the five selected, not the 49 possible results. You then compute the quotient and remainder based on the range of a single value (0 to size inclusive in this case, so size + 1 possible values), and that gets the high and low results cheaply.

The performance differences are stark; comparing:

def unique_random_pairs_by_product(size):
    return random.sample(list(itertools.product(range(size+1), repeat=2)), 5)

to:

def unique_random_pairs_optimized(size):
    val_range = size + 1
    return [divmod(x, val_range) for x in random.sample(range(val_range * val_range), 5)]

the optimized version takes about 15% less time even for an argument of 6 (~4.65 μs for product, ~3.95 μs for optimized). But at size of 6, you're not seeing the scaling factor at all. For size=100, optimized only increases to ~4.35 μs (the time increasing slightly because the larger range is more likely to have to allocate new ints, instead of using the small int cache), while product jumps to 387 μs, a nearly 100x difference. And for size=1000, the time for product jumps to 63.8 ms, while optimized remains ~4.35 μs; a factor of 10,000x difference in runtime (and an even higher multiplier on memory usage). If size gets any larger than that, the product-based solution will quickly reach the point where the delay from even a single sampling is noticeable to humans; the optimized solution will continue to run with identical performance (modulo incredibly tiny differences in the cost of the divmod).

user_3646960
Related