By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,846 Members | 1,862 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,846 IT Pros & Developers. It's quick & easy.

Fastest Way To Iterate Over A Probability Simplex

P: n/a
Hello,

Let's say a probability vector of dimension d is x_1, ..., x_d, where
each one is a non-negative term, and they all sum up to 1. Now I'd like
to iterate over all probability vectors, but this is impossible, since
they're uncountable. So instead, let's say I want to iterate over all
such vectors under the constraint that the granularity of each component
is at most some delta.

To make things pythonesque, here's the interface:
<interface>
class simplex:
def __init__(self, dim, delta):
...

def __iter__(self):
...

def next(self):
...
</interface>

The problem is, what's a fast implementation? I tried something simple,
and it is slooooooooooooow. If anyone can think of something clever, I'd
love to hear it.

Many Thanks,

Efrat
May 22 '07 #1
Share this Question
Share on Google+
2 Replies


P: n/a
On May 22, 11:19 am, Efrat Regev:
I want to iterate over all
such vectors under the constraint that the granularity of
each component is at most some delta.
You can think of this like your sum is an integer>=1 and the single
"probabilities" are integers>=1 So given the sum, like 6, you can find
all the parts of it, and then find all the permutations of such parts.
Eppstein has given code for the parts of an integer, and you can can
find the iterable permutations code on the cookbook. But the number of
such possible vectors grows very quickly...

http://aspn.activestate.com/ASPN/Coo.../Recipe/218332
http://aspn.activestate.com/ASPN/Coo.../Recipe/474124

Bye,
bearophile

May 22 '07 #2

P: n/a
be************@lycos.com wrote:
On May 22, 11:19 am, Efrat Regev:
>I want to iterate over all
such vectors under the constraint that the granularity of
each component is at most some delta.

You can think of this like your sum is an integer>=1 and the single
"probabilities" are integers>=1 So given the sum, like 6, you can find
all the parts of it, and then find all the permutations of such parts.
Eppstein has given code for the parts of an integer, and you can can
find the iterable permutations code on the cookbook. But the number of
such possible vectors grows very quickly...

http://aspn.activestate.com/ASPN/Coo.../Recipe/218332
http://aspn.activestate.com/ASPN/Coo.../Recipe/474124

Bye,
bearophile
Many thanks. I modified the recipes you attached some, and it works much
better. Nice and informative answer!
May 22 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.