Python: create list of random integers where state space is limted

Question

I would like to create a list of x random integers which are chosen from the interval [0,n[ (n is usually much bigger than x) whereby certain numbers of this interval should be ignored. I implemented that as follows:

from random import randint

def createRandomList(n, x, ignore=[]):
    myList = []
    while len(myList) < x:
        tempr = randint(0,n-1)
        if tempr not in ignore:
            myList.append(tempr)
    return myList

When I then call

l = createRandomList(5,2,ignore=[2,3])

I obtain e.g.

l = [1,4] #2 and 3 should not appear

or

l = [0,1]

or

l = [4,4]

or ...

That is the desired outcome, however, is there any faster/more compact way to do this?

EDIT: All of these solutions work fine, so I had to do some speed comparisons to decide which one to accept. It turns out - not very surprisingly - that generating all the allowed values beforehand and then choosing from them, is very inefficient for large values of n and the while-loops win easily. Therefore, I accepted hgwells answer since his version is not only faster than my while-loop but should also consume less memory.

Thanks a lot for all the answers; I could learn a lot from all of them!

If you don't need the whole list at once, you can use generators. https://docs.python.org/2/howto/functional.html — Robert Jacobs, May 27 '15 at 16:33
It might make it a bit faster if `ignore` was a `set` instead of a `list`. — Moshe, May 27 '15 at 16:38
@RobertJacobs: Thanks for the suggestion, I will read about it. — Cleb, May 27 '15 at 16:45
Just FYI: do not use a default empty list (ignore=[]) it has some non intuitive consequences. http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument — ashwinjv, May 27 '15 at 16:46
@Moshe: Why did you delete your answer? It worked fine. You just confused x and n in srcList and destList - just a small typo :). I will check whether that speeds it up. — Cleb, May 27 '15 at 16:46
@hgwells: That's not an issue here: `ignore` is not being modified or returned or anything like that. — , May 27 '15 at 16:46
@Cleb: Since you know how long the list is, I think I would first initialize the list to the correct size (e.g. `mylist = [0] * x`) and then overwrite its entries with random values, rather than build the list by appending to it. I expect this to perform better if `x` is large, as it would avoid reallocations. (of course, this whole issue is obviated if you use the generator-based approach) — , May 27 '15 at 16:49
@Hurkyl: Could you elaborate on the generator-based approach, please? — Cleb, May 27 '15 at 16:53
@Cleb Because he specifically asked in the question's title: "where state space is limted". My solution required large amounts of memory. — Moshe, May 28 '15 at 12:21
@Moshe: I am sorry for that, seems "state space" was misleading. What I meant was the state space of the random numbers since I do not want all numbers from a certain range but only from a reduced state space... — Cleb, May 28 '15 at 13:01

score 1 · Answer 1 · answered May 27 '15 at 16:33

Depending on the values for n, x, and ignore, it might be more efficient to build a list of all allowed values and use repeated calls to random.choice() to create your list.

For example, one (albeit slow) implementation would be:

def createRandomList(n, x, ignore=[]):
    srcList = [i for i in range(n) if i not in ignore]
    destList = [random.choice(srcList) for i in range(x)]
    return destList

score 1 · Answer 2 · answered May 27 '15 at 16:57

1

from random import randint

def createRandomList(n, x, ignore=[]):
    available_numbers = [elem for elem in range(n) if elem not in ignore]
    myList = [available_numbers[randint(0, len(available_numbers) - 1)] for _ in range(x)]
    return myList

In this method, firstly you create list of numbers from 0 to n-1, without numbers in ignore. After that, you chose x numbers from this list.

answered May 27 '15 at 16:57

Mikhail

395
3
17

That works fine, it seems. Alternatively, one could replace available_numbers[randint(0, len(available_numbers) - 1) by choice(available_numbers). Not sure which is better. I'll wait with accepting this answer for a while to see whether someone posts a generator-based solution that was mentioned in the comments above. – Cleb May 27 '15 at 17:11

ashwinjv · Accepted Answer · 2015-05-27T18:41:48.527

1

Here is a generator-based solution. But I dont really know how much it would improve your solution

from random import randint

def randGen(n, x, ignore=[]):
    index = 0
    while index < x:
        temp = randint(0, n-1)
        if temp not in ignore:
            index += 1
            # yield the temp value and wait for
            # the next call
            yield temp

# you could now create your list 
# myList = [i  for i in randGen(5, 2, [2,3])]
# or as Mark pointed out
myList = list(randGen(5,2,[2,3]))
print(myList)

# or use the generator items when you need them
for i in randGen(5, 2, [2,3]):
    # do something with i
    print(i)

edited May 27 '15 at 18:41

answered May 27 '15 at 17:24

ashwinjv

2,787
1
23
32

1

I keep forgetting that you can do `list(...)` instead of `[i for i in ...]` too. – Mark Ransom May 27 '15 at 18:07
Thanks for providing such an example. I'll upvote and decide later which answer to accept since I like all three of them ;) – Cleb May 28 '15 at 08:16

score 1 · Answer 4 · answered May 27 '15 at 17:56

An itertools-based generator approach:

from itertools import count, islice, ifilterfalse  # just 'filterfalse' in Py3
from random import randint
def random_list(limit, size, ignore={}):  # ignore should be a set for O(1) lookups
    ints = (randint(0, limit-1) for _ in count())  # generate randints in range
    filtered = ifilterfalse(ignore.__contains__, ints)  # filter out the rejects
    for i in islice(filtered, size):  # limit the size to what we want and yield
        yield i
    # in Python 3 you don't need the for-loop, simply:
    # yield from islice(filtered, size) 

print list(random_list(5, 2, {2, 3})
# [1, 4]

This can just be stacked into a one-liner, but breaking it out makes for better readability:

l = list(islice(ifilterfalse({2, 3}.__contains__, (randint(0, 4) for _ in count())), 2))

This is a very instructive example, thanks a lot for that! I'll upvote it for now and decide later which answer to accept. — Cleb, May 28 '15 at 08:15

Python: create list of random integers where state space is limted

4 Answers4