33

I have taken a count of something and it came out to N.

Now I would like to have a list, containing 1 to N numbers in it.

Example:

N = 5

then, count_list = [1, 2, 3, 4, 5]

Also, once I have created the list, I would like to randomly select a number from that list and use that number.

After that I would like to select another number from the remaining numbers of the list (N-1) and then use that also.

This goes on it the list is empty.

txemsukr
  • 1,017
  • 1
  • 10
  • 32
Sunny
  • 7,444
  • 22
  • 63
  • 104
  • Your list contains 1 through N, not zero through N. – Fred Foo Sep 27 '11 at 10:08
  • How big do you expect N to be? 10? 10^8? This matters; all the answers provided assume O(N) space complexity...are you sure you want this? In your question you're quite explicit in saying "Now I would like to have a list", but I wanted to make sure you realised what this means. – Asim Ihsan Sep 27 '11 at 10:14
  • I never thought that deep. I was acttually looking for a list where N is max about 20 to 30. But since u have mentioned this, as a learning exercise for me, could you please help me with the following: 1. wht is O(N) space complexity? 2, what happens when my list is about 10^8 – Sunny Sep 27 '11 at 11:09
  • 2
    You can take a look at http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o about Big O. And about a N=10^8... simply try to run your program first as N=10^5, then N=10^6, etc... You will see the difference without measuring. – Gandi Sep 27 '11 at 11:24
  • 2
    @Sunny: Gandi's link is excellent, but a bit long and technical. Short answer: Big O means "if I have N more elements, how much more expensive will my process become?". People usually focus on "time complexity", i.e. how long it takes, but almost always forget about "space complexity", i.e. how much memory it requires. Trust me - an array with 100 million integers takes up a lot of RAM in Python! :) I just run "range(10 ** 8)" in a shell and it takes up 1.6GB!. – Asim Ihsan Sep 27 '11 at 11:42

8 Answers8

41

You can create the enumeration of the elements by something like this:

mylist = list(xrange(10))

Then you can use the random.choice function to select your items:

import random
...
random.choice(mylist)

As Asim Ihsan correctly stated, my answer did not address the full problem of the OP. To remove the values from the list, simply list.remove() can be called:

import random
...
value = random.choice(mylist)
mylist.remove(value)

As takataka pointed out, the xrange builtin function was renamed to range in Python 3.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Constantinius
  • 34,183
  • 8
  • 77
  • 85
7

You can try this code

import random
N = 5
count_list = range(1,N+1)
random.shuffle(count_list)

while count_list:
    value = count_list.pop()
    # do whatever you want with 'value'
2

As for the first part:

>>> N = 5
>>> count_list = [i+1 for i in xrange(N)]
>>> count_list
[1, 2, 3, 4, 5]
>>>

As for the second, read 9.6. random — Generate pseudo-random numbers.

>>> from random import choice
>>> a = choice(count_list)
>>> a
1
>>> count_list.remove(a)
>>> count_list
[2, 3, 4, 5]

That's the general idea.

By the way, you may also be interested in reading Random selection of elements in a list, with no repeats (Python recipe).

There are a few implementations of fast random selection.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Gandi
  • 3,522
  • 2
  • 21
  • 31
1

Maintain a set and remove a randomly picked-up element (with choice) until the list is empty:

s = set(range(1, 6))
import random

while len(s) > 0:
  s.remove(random.choice(list(s)))
  print(s)

Three runs give three different answers:

>>>
set([1, 3, 4, 5])
set([3, 4, 5])
set([3, 4])
set([4])
set([])
>>>
set([1, 2, 3, 5])
set([2, 3, 5])
set([2, 3])
set([2])
set([])

>>>
set([1, 2, 3, 5])
set([1, 2, 3])
set([1, 2])
set([1])
set([])
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
kiriloff
  • 25,609
  • 37
  • 148
  • 229
1

You don't need to count stuff if you want to pick a random element. Just use random.choice() and pass your iterable:

import random
items = ['foo', 'bar', 'baz']
print random.choice(items)

If you really have to count them, use random.randint(1, count+1).

patrys
  • 2,729
  • 17
  • 27
1

You can use:

import random
random.choice(range(n))

or:

random.choice(range(1,n+1))

if you want it from 1 to n and not from 0.

Guy
  • 14,178
  • 27
  • 67
  • 88
1

After that I would like to select another number from the remaining numbers of the list (N-1) and then use that also.

Then you arguably do not really want to create a list of numbers from 1 to N just for the purpose of picking one (why not just ask for a random number in that range directly, instead of explicitly creating it to choose from?), but instead to shuffle such a list. Fortunately, the random module has you covered for this, too: just use random.shuffle.

Of course, if you have a huge list of numbers and you only want to draw a few, then it certainly makes sense to draw each using random.choice and remove it.

But... why do you want to select numbers from a range, that corresponds to the count of some items? Are you going to use the number to select one of the items? Don't do that; that's going out of your way to make things too complicated. If you want to select one of the items, then do so directly - again with random.choice.

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
0

Create the list (edited):

count_list = range(1, N+1)

Select random element:

import random
random.choice(count_list)
pvoosten
  • 3,247
  • 27
  • 43