P: n/a

Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
BEGIN PGP SIGNATURE
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla  http://enigmail.mozdev.org
iD8DBQFG0zdFldnAQVacBcgRAg/yAJ9ZVWfDptl4Qxl+kSIpZqoi00qNYgCg+YNf
jVEXRG+grsbVDrRH1wXSw14=
=mGlJ
END PGP SIGNATURE  
Share this Question
P: n/a

How about decorating your list of elements with an additional value,
which indicates the weight of that element. A value of 1 will indicate
'as likely as any other', < 1 will be 'less likely than' any other and
1 will be 'more likely than any other'. Then create a sorted list
based on the combined value of weight and the output of random(); from
this take the first N many elements to meet your requirements.
hth
Jon
On 27 Aug, 21:42, Ivan Voras <ivoras@__fer.hr__wrote:
Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
signature.asc
1KDownload
 
P: n/a

Ivan Voras wrote:
Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
That's weird. random.randint(a,b) will be enough for most cases. Test
your system to see the distribution is uniform with something like:

import random
dist = {}
for z in xrange(100000):
u = random.randint(1,10)
try:
dist[u] = dist[u] + 1
except KeyError:
dist[u] = 1
print dist
  
P: n/a

On 20070827, Jungeun Park <ju**********@gmail.comwrote:
>I have a list of items, and need to choose several elements from it, "almost random". The catch is that the elements from the beginning should have more chance of being selected than those at the end (how much more? I don't care how the "envelope" of probability looks like at this point  can be linear). I see that there are several functions in Python standard libraries for various distribution, but is there an easy pythonic way to make them do what I need?
That's weird. random.randint(a,b) will be enough for most
cases. Test your system to see the distribution is uniform
with something like:
Except he wants a nonuniform distribution.

Grant Edwards grante Yow! I'm changing the
at CHANNEL ... But all I get
visi.com is commercials for "RONCO
MIRACLE BAMBOO STEAMERS"!  
P: n/a

On Aug 27, 3:42 pm, Ivan Voras <ivoras@__fer.hr__wrote:
Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
signature.asc
1KDownload
If your list is small enough, you could do something
like this:
import random
test = ['a','b','c','d','e','f','g','h','i','j']
temp = []
size = len(test)1
for i,j in enumerate(test):
temp.extend(j*(2**(sizei)))
for i in xrange(400):
if i % 30 == 0: print
print random.choice(temp),
## a a b a a a i c a a a b c b b a a a a b a a a d a b a a g f
## a e a a a i a b a a b c b a a b a b b c b a b a c a a a a a
## b a a c a c e d b d a a a a a c a b b e a a b a a b a a c a
## a a a a a a b a b a c a a a c a d a c a a d b b b b d a a a
## a a d b a a a b a b b a b a c a a a b b a c b c a a c c c a
## a a b a a a b a b a a a a d c a a b c b b b d b b a a b c a
## a a a a a a b a d b c d b a b c a d b b b a b a b b b b b a
## b c a b a a b c a a a a a a a a b a a a b a a a a a d a b b
## a b b a c a b c a a a a a a a a c b a c c a a e a a a c b b
## a c e b b a a b c a b a b a a b a g a b e a a a c c a a c b
## b i a b a a a a c c c b a a a a a b b b a b b a a b b h a a
## d b a b a b b a a b c a b a a b a a a c a d a a b a b a a a
## a d a b b a b a a c a b c d b a a d a a b b a a a a a d a c
## a a a b a a b a c b
Here, 'a' is twice as likely to occur as 'b',
which is twice as likely to occur as 'c',
which is twice as likely to occur as 'd',
etc.  
P: n/a

On 8/27/07, J. Cliff Dyer <jc*@sdf.lonestar.orgwrote:
Play with your log to get the range you want
Here you can get "true" random numbers (not pseudorandom, they claim
to use a quatum generaton (?)) by fetching them from: http://random.irb.hr/
They give you a python class t insert into your code, but you need to
register to use it (free).
I am not affiliated to them in any way, I just used it once to play
with it and it worked.
Best,

Sebastián Bassi (セバスティアン)
Diplomado en Ciencia y Tecnolog*a.
GPG Fingerprint: 9470 0980 620D ABFC BE63 A4A4 A3DE C97D 8422 D43D  
P: n/a

Jungeun Park wrote:
Ivan Voras wrote:
>Hi,
I have a list of items, and need to choose several elements from it, "almost random". The catch is that the elements from the beginning should have more chance of being selected than those at the end (how much more? I don't care how the "envelope" of probability looks like at this point  can be linear). I see that there are several functions in Python standard libraries for various distribution, but is there an easy pythonic way to make them do what I need?
That's weird. random.randint(a,b) will be enough for most cases. Test
your system to see the distribution is uniform with something like:
The distribution is uniform. However, he wants a way to get nonuniform sampling
of that list.

Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
 Umberto Eco  
P: n/a

Ivan Voras wrote:
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
import random
def choose(samples, **kwargs):
total = sum(kwargs.values())
result = []
for n in range(samples):
choice = random.random() * total
for key, weight in kwargs.iteritems():
choice = weight
if choice <= 0:
result.append(key)
total = kwargs.pop(key)
break
else:
raise ValueError('Too many samples taken from the universe')
return result
print choose(3, a=1, b=2, c=2, d=1, e=3)
Scott David Daniels Sc***********@Acm.Org  
P: n/a

Jungeun Park wrote:
Ivan Voras wrote:
>Hi,
I have a list of items, and need to choose several elements from it, "almost random". The catch is that the elements from the beginning should have more chance of being selected than those at the end (how much more? I don't care how the "envelope" of probability looks like at this point  can be linear). I see that there are several functions in Python standard libraries for various distribution, but is there an easy pythonic way to make them do what I need?
That's weird. random.randint(a,b) will be enough for most cases. Test
your system to see the distribution is uniform with something like:

import random
dist = {}
for z in xrange(100000):
u = random.randint(1,10)
try:
dist[u] = dist[u] + 1
except KeyError:
dist[u] = 1
print dist

I understood the question wrong.(Thanks, Grant and Robert.) To get the
linear
distribution, you can start from the following:
a = (random.random() + random.random())/2.0 # Triangle distribution
in [0,1)
b = random.random() #
Uniform in [0,1)
c = b + (1b)*a
# Convolution
u = int(100*(1c)+1)
# ceil(100*(1c))
, then, because convolution of a rectangle function and a triangle
function is a
linear function under the valid domain, u is a random integer in [1,100]
that follows (decreasing) linear distribution.
Alternatively if I were in your case, I would go with an exponential
random with
a suitable lambda(by cutting its tail.)  
P: n/a

En Mon, 27 Aug 2007 17:42:45 0300, Ivan Voras <ivoras@__fer.hr__>
escribi�:
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
Using a linear (or triangular) distribution:
 begin 
from random import randint
def biased_choice(values):
"""Choose a random element from values;
first elements are chosen more frequently than later ones.
Weights are linearly assigned; given n elements, the first
has weight n, second has n1, ... last has weight 1.
"""
n = len(values)
sumw = ((n + 1) * n) // 2
x = randint(1, sumw)
F = 0
for i in xrange(1, n+1):
F += i
if x<=F: return values[i]
# test
from collections import defaultdict
values = ["a", "b", "c", "d", "e"]
stats = defaultdict(int)
for i in xrange(150000):
stats[biased_choice(values)] += 1
for key in sorted(stats):
print key, stats[key]
 end 
Output:
a 50023
b 39869
c 30256
d 19784
e 10068

Gabriel Genellina  
P: n/a

On Mon, 27 Aug 2007 22:42:45 +0200, Ivan Voras wrote:
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
If you really just want to tend towards the beginning of the list, and
don't care what the envelope looks like, how about this:
def biasedselection(thelist):
index = random.random() * random.random() * len(thelist)
# or index random.random() ** 2 * len(thelist)
return thelist[index]
Dan

Dan Sommers A death spiral goes clock
<http://www.tombstonezero.net/dan/ wise north of the equator.
Atoms are not things.  Werner Heisenberg  Dilbert's PHB  
P: n/a

On Aug 27, 4:42 pm, Ivan Voras <ivoras@__fer.hr__wrote:
Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
Not sure how pythonic it is...but a simple(?) way to increase the
chances for particular
elements is to introduce copies. For example given [1,2,3], you can
increase the chances
of selecting '1' by changing the list to [1,1,2,3].
Cheers
Chris  
P: n/a

Ivan Voras wrote:
Hi,
I have a list of items, and need to choose several elements from it,
"almost random". The catch is that the elements from the beginning
should have more chance of being selected than those at the end (how
much more? I don't care how the "envelope" of probability looks like at
this point  can be linear). I see that there are several functions in
Python standard libraries for various distribution, but is there an easy
pythonic way to make them do what I need?
If you take the difference between two uniformly distributed random
variables, the probability density function forms an isosceles triangle
centered at 0. Take the absolute value of that variable and the pdf is a
straight line with maximum value at 0 tapering to 0 at max. Thus,
z = abs(randint(0, max)  randint(0, max))
ought to do the trick.

Jeffrey Barish  
P: n/a

Jeffrey Barish wrote:
If you take the difference between two uniformly distributed random
variables, the probability density function forms an isosceles triangle
centered at 0. Take the absolute value of that variable and the pdf isa
straight line with maximum value at 0 tapering to 0 at max. Thus,
z = abs(randint(0, max)  randint(0, max))
ought to do the trick.
It's elegant :)
I've noticed something interesting in my test: the value 0 appears less
often than other values (which behave as they should). I wrote this test
script:
from random import randint
map = {}
for x in xrange(11):
map[x] = 0
for a in xrange(500):
x = abs(randint(0, 10)  randint(0, 10))
map[x] += 1
print map
and here are some results:
python a.py
{0: 49, 1: 66, 2: 72, 3: 73, 4: 64, 5: 55, 6: 40, 7: 36, 8: 18, 9: 18,
10: 9}
python a.py
{0: 34, 1: 90, 2: 77, 3: 61, 4: 56, 5: 52, 6: 42, 7: 34, 8: 27, 9: 15,
10: 12}
python a.py
{0: 33, 1: 80, 2: 84, 3: 62, 4: 52, 5: 46, 6: 51, 7: 31, 8: 35, 9: 16,
10: 10}
python a.py
{0: 50, 1: 100, 2: 69, 3: 53, 4: 63, 5: 47, 6: 41, 7: 26, 8: 30, 9: 11,
10: 10}
python a.py
{0: 31, 1: 84, 2: 70, 3: 70, 4: 74, 5: 50, 6: 38, 7: 28, 8: 31, 9: 15,
10: 9}
python a.py
{0: 43, 1: 101, 2: 79, 3: 66, 4: 41, 5: 59, 6: 37, 7: 30, 8: 26, 9: 15,
10: 3}
python a.py
{0: 44, 1: 108, 2: 74, 3: 50, 4: 53, 5: 54, 6: 39, 7: 34, 8: 28, 9: 13,
10: 3}
python a.py
{0: 42, 1: 72, 2: 70, 3: 72, 4: 61, 5: 54, 6: 41, 7: 36, 8: 30, 9: 15,
10: 7}
If I ignore the case when the delta is 0, it works fine, but I don't
understand why should the 0case happen less often than others.
BEGIN PGP SIGNATURE
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla  http://enigmail.mozdev.org
iD8DBQFG1yC5ldnAQVacBcgRAg6CAKCm4HB5AFHtwRgLHTgB4f cpgA3AsQCferjS
PHe06TZqYJoH/dybU7mIN9o=
=VIwB
END PGP SIGNATURE  
P: n/a

On Aug 30, 3:55 pm, Ivan Voras <ivoras@__fer.hr__wrote:
I've noticed something interesting in my test: the value 0 appears less
often than other values (which behave as they should).
That's because the call to abs() usually collapses two values to one
(e.g. 2 and 2 both end up being 2),
but there's only one integer n for which abs(n) == 0.
One possible fix: do
x = randint(0, 10)  randint(0, 10)
x = abs(x)  (x<0)
This collapses 1 and 0 to 0, 2 and 1 to 1, etc.
Mark  
P: n/a

Ivan Voras wrote:
Jeffrey Barish wrote:
>If you take the difference between two uniformly distributed random variables, the probability density function forms an isosceles triangle centered at 0. Take the absolute value of that variable and the pdf is a straight line with maximum value at 0 tapering to 0 at max. Thus,
z = abs(randint(0, max)  randint(0, max))
ought to do the trick.
It's elegant :)
I've noticed something interesting in my test: the value 0 appears less
often than other values (which behave as they should).
The distribution of the difference (before the abs()) looks like this (max=4):
#
###
#####
#######
0+++
321 123
Taking the absolute value doubles up the nonzero masses, but there's no
"negative 0" to add to the 0s stack.
#
#
###
###
####
####
0123
The method does not work because of that.

Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
 Umberto Eco  
P: n/a

One possible fix: do
>
x = randint(0, 10)  randint(0, 10)
x = abs(x)  (x<0)
This collapses 1 and 0 to 0, 2 and 1 to 1, etc.
Or a slightly simpler formula that ends up producing the same
distribution:
x = min(randint(0, 10), randint(0, 10))
Mark  
P: n/a

Robert Kern wrote:
Ivan Voras wrote:
>Jeffrey Barish wrote:
>>If you take the difference between two uniformly distributed random variables, the probability density function forms an isosceles triangle centered at 0. Take the absolute value of that variable and the pdf is a straight line with maximum value at 0 tapering to 0 at max. Thus,
z = abs(randint(0, max)  randint(0, max))
ought to do the trick.
It's elegant :)
I've noticed something interesting in my test: the value 0 appears less often than other values (which behave as they should).
The distribution of the difference (before the abs()) looks like this
(max=4):
#
###
#####
#######
0+++
321 123
Taking the absolute value doubles up the nonzero masses, but there's no
"negative 0" to add to the 0s stack.
#
#
###
###
####
####
0123
The method does not work because of that.
The math says that it works, so we must not be implementing it correctly. I
suspect that our mistake is quantizing the random variable first and then
taking the difference and absolute value. What result do you get when you
quantize once? That is, obtain two random values (floats) with uniform
pdf. Take the difference. Abs. Round to int. This way, everything in the
band from (0.5, +0.5) goes to 0, and that's the highest part of the
triangle.

Jeffrey Barish  
P: n/a

Mark Dickinson wrote:
That's because the call to abs() usually collapses two values to one
(e.g. 2 and 2 both end up being 2),
but there's only one integer n for which abs(n) == 0.
Ah. Need to sleep more.
BEGIN PGP SIGNATURE
Version: GnuPG v1.2.5 (MingW32)
Comment: Using GnuPG with Mozilla  http://enigmail.mozdev.org
iD8DBQFG2EtmldnAQVacBcgRAj4kAJ9MHofb5nXj9E2nZ4AFi/zoj+MPYQCgn3ii
xpgzHsrFPztv/Ni7Jp3KuXA=
=MhAM
END PGP SIGNATURE  
P: n/a

Jeffrey Barish wrote:
Robert Kern wrote:
>Ivan Voras wrote:
>>Jeffrey Barish wrote:
If you take the difference between two uniformly distributed random variables, the probability density function forms an isosceles triangle centered at 0. Take the absolute value of that variable and the pdf is a straight line with maximum value at 0 tapering to 0 at max. Thus,
z = abs(randint(0, max)  randint(0, max))
ought to do the trick. It's elegant :)
I've noticed something interesting in my test: the value 0 appears less often than other values (which behave as they should).
The distribution of the difference (before the abs()) looks like this (max=4):
# ### ##### ####### 0+++ 321 123
Taking the absolute value doubles up the nonzero masses, but there's no "negative 0" to add to the 0s stack.
# # ### ### #### #### 0123
The method does not work because of that.
The math says that it works, so we must not be implementing it correctly.
"The math" says nothing of the kind about the method that was stated.
I
suspect that our mistake is quantizing the random variable first and then
taking the difference and absolute value. What result do you get when you
quantize once? That is, obtain two random values (floats) with uniform
pdf. Take the difference. Abs. Round to int. This way, everything in the
band from (0.5, +0.5) goes to 0, and that's the highest part of the
triangle.
That's a very different "it". The difference is not just implementation.
If you change "round" to "truncate", that method should work, though.

Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
 Umberto Eco  
P: n/a

I'm sorry that I took the time to respond.

Jeffrey Barish  
P: n/a

Jeffrey Barish wrote:
I'm sorry that I took the time to respond.
I'm sorry. I didn't intend my post to be as harsh as it was.

Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
 Umberto Eco   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 3408
 replies: 22
 date asked: Aug 27 '07
