Choose random element in list influenced by its position

Question

I had a list with four elements and to choose one of them maximizing chances of the first elements I did this:

from random import choice
_list = [19,14,29,3]
element = choice((a[0],a[0],a[0],a[0],a[1],a[1],a[1],a[2],a[2],a[3]))

Although now the number of elements in _list is variable, trying to preserve the same behavior of before I coded this piece:

from random import choice
_list = [19,14,29,3,.......] # n elements
weighted = []
for i in range(len(_list)):
    for j in range(len(_list)-i):
        weighted.append(_list[i])
element = choice(weighted)

Are there any other methods that can achieve the same result with less code and be more efficient? Because I think that if n gets too big, then weighted will be enormous and will slow down my algorithm.

This might be helpful, though you'd have to do a little bit of extra work to make the existing answers work with your input: http://stackoverflow.com/q/3679694/646543 — Michael0x2a, Jun 17 '14 at 05:25

score 2 · Accepted Answer · answered Jun 17 '14 at 05:53

There's actually a built-in function that does this for you:

random.triangular(0, length, 0)

Here's the documentation for that function

If you want to write it yourself, you can actually do this without using any loops at all. It's easy to see how if you look at it correctly. For example, with 6 elements, you could visualize it like this:

|
| |
| | |
| | | |
| | | | |
| | | | | |
0 1 2 3 4 5

If we flip this around and put it back together, we could get a rectangle:

5 4 3 2 1 0
| | | | | |
- | | | | |
| - | | | |
| | - | | |
| | | - | |
| | | | - |
| | | | | -
| | | | | |
0 1 2 3 4 5

For a list of length 6, the rectangle has height 7 and width 6. So you just need to pick two random integers and figure out which number that coordinate belongs to. This can be done with a simple calculation - all of the coordinates right below the break have x+y equal to n-1, while all of the coordinates right above the break have x+y equal to n. Without further ado, here's the code:

def triangle_random(count):
    x = random.randint(0, count-1) # randint includes both ends, so we need count-1
    y = random.randint(0, count)
    if x + y < count:
        return x
    else:
        return count-1 - x

Both your solutions work, although in the first, using `random.triangular()` can lead to a element out of the list index as it considers both ends of the triangle in the x-axis, I had to add a condition that if that occurs the function runs again. Also the first solution approximates very well the original behavior but it is not perfect. The second one is perfect! — Rodrigo Oliveira, Jun 17 '14 at 16:44

Rodrigo Oliveira · Answer 2 · 2014-06-20T19:00:46.823

@RobWatts gave a great and neat answer by using geometry, but I also found another way to get the same results efficiently:

import random
_list = [1,2,3,4]
S = (len(_list)+1)*len(_list)/2 # This represents the Sum of what would be the 'weighted' list composed by elements following a(0) = 1 and a(n) = a(n-1)+1 conditions
x = random.randint(1,S) # pick one element from what would be 'weighted' list 
last = 0
for i in range(len(_list)): # get which element in _list 'x' points out
    if( x <= len(_list)-i+last ): # first 'len(_list)' elements point out to _list[0], then the next len(_list)-1 elements to _list[1] and so on
        element1 = _list[i]
        break
    else: last += len(_list)-i

Choose random element in list influenced by its position

2 Answers2