Fastest Way To Iterate Over A Probability Simplex

Efrat Regev efrat_regev at yahoo.com
Tue May 22 05:19:31 EDT 2007


	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



More information about the Python-list mailing list