> Since integers are chosen uniformly, this would guarantee (?) that the
> polynomial is generated uniformly. Only hitch is that I don't know if
> there is such inttovec is in in SAGE yet. mhansen, any idea?
Yes, this is pretty much what I'm doing. While I don't have those
exact functions, they would be easy to implement.
How fast do these need to be? Here's a rough function that uniformly
selects monomials without replacement from all possible monomials with
degree less than d.
def random_monomials(n, degree, terms):
#Get the counts of the total number of monomials
#of degree d
counts = [1] #degree 0
for d in range(1, degree):
counts.append(binomial(n+d-1, d))
total = sum(counts)
#Select a random indices
indices = sample(xrange(total), terms)
monomials = []
for random_index in indices:
#Figure out which degree it corresponds to
d = 0
while random_index >= counts[d]:
random_index -= counts[d]
d += 1
#Generate the corresponding monomial
comb = choose_nk.from_rank(random_index, n+d-1, n-1)
monomial = [ comb[0] ]
monomial += map(lambda i: comb[i+1]-comb[i]-1, range(n-2))
monomial.append( n+d-1-comb[-1]-1 )
monomials.append(monomial)
return monomials
Here's an example:
sage: time random_monomials(20, 40, 20)
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.09
[[8, 1, 5, 0, 0, 1, 2, 0, 1, 1, 2, 0, 0, 2, 4, 2, 1, 4, 3, 1],
[0, 0, 9, 2, 0, 7, 2, 0, 3, 2, 1, 0, 3, 1, 0, 1, 4, 0, 4, 0],
[0, 0, 3, 0, 1, 4, 3, 1, 0, 2, 1, 3, 4, 1, 1, 0, 6, 7, 0, 0],
[0, 2, 3, 0, 0, 2, 1, 2, 5, 3, 0, 0, 1, 5, 2, 0, 1, 1, 9, 0],
[0, 1, 1, 7, 0, 1, 6, 0, 1, 0, 1, 0, 1, 6, 2, 0, 7, 0, 2, 1],
[7, 0, 3, 1, 0, 6, 1, 4, 0, 8, 0, 0, 0, 0, 0, 1, 3, 3, 0, 0],
[0, 0, 0, 4, 1, 5, 3, 1, 1, 0, 0, 2, 3, 3, 3, 1, 4, 0, 1, 6],
[1, 2, 5, 0, 5, 1, 1, 0, 0, 7, 0, 1, 1, 1, 1, 2, 3, 4, 1, 0],
[1, 7, 0, 0, 4, 3, 0, 2, 0, 0, 1, 8, 1, 1, 0, 0, 2, 5, 0, 0],
[0, 4, 0, 3, 5, 0, 0, 0, 1, 0, 1, 3, 2, 1, 8, 4, 0, 0, 1, 0],
[1, 0, 9, 0, 1, 7, 3, 1, 2, 0, 0, 1, 0, 0, 5, 1, 0, 6, 0, 0],
[1, 3, 0, 3, 5, 0, 1, 2, 0, 2, 4, 1, 0, 4, 1, 2, 3, 1, 4, 0],
[0, 2, 3, 8, 1, 0, 3, 1, 0, 1, 1, 1, 0, 1, 5, 5, 1, 5, 0, 0],
[3, 0, 4, 0, 8, 0, 3, 1, 0, 2, 0, 1, 0, 3, 1, 6, 2, 2, 0, 1],
[2, 5, 1, 0, 1, 0, 2, 5, 1, 2, 3, 3, 0, 0, 0, 4, 4, 0, 0, 0],
[1, 0, 6, 2, 5, 0, 0, 0, 1, 4, 2, 0, 5, 0, 1, 1, 0, 0, 3, 4],
[1, 1, 0, 2, 0, 1, 1, 1, 3, 3, 2, 2, 1, 0, 0, 1, 1, 1, 11, 7],
[7, 0, 3, 0, 4, 1, 2, 1, 6, 0, 0, 1, 3, 1, 0, 0, 7, 3, 0, 0],
[1, 2, 3, 1, 0, 1, 0, 0, 3, 3, 2, 0, 5, 0, 0, 0, 3, 1, 2, 7],
[0, 5, 0, 3, 1, 1, 2, 0, 1, 1, 0, 1, 4, 2, 8, 2, 2, 1, 0, 2]]
--Mike
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
