2007/10/25, Martin Albrecht <[EMAIL PROTECTED]>:
> This construction is random if the random number generator ("randint") is
> random. Btw. how random is randint?
The core generator for all random functions in Python uses the
mersenne twister which is pretty strong.
I have another suggestion for this problem, that looks somewhat like
yours. Maple has 2 functions in its combinatorics package that :
inttovec(number,nvars) which turns a number into vector of length
nvars, and vectotint(vec) that does the opposite. Here's the
documentation for them:
"""
These two functions provide a one-to-one correspondence between the
non-negative integers and all vectors composed of n non-negative
integers.
The one-to-one correspondence is defined as follows. View all vectors
of n non-negative integers as exponent vectors on n variables.
Therefore, for each vector, there is a corresponding monomial.
Collect all such monomials and order them by increasing total
degree. Resolve ties by ordering monomials of the same degree in
lexicographic order. This gives a canonical ordering.
"""
Ex:
> inttovec(9,2);
[0, 3]
> vectoint([0,3]);
9
Now the idea is simple: for random_elements(deg,terms) , generate the
a number randomly in (0, nchoosek(n+d-1,d)) and compute the
corresponding monomial:
for t in terms:
num = randint(0, nchoosek(n+d-1,d))
term = inttovec(num,nvars)
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?
didier
>
> Now we need to choose a degree d at random. We cannot do this uniformly at
> random because the classes (associated to the degree) are not of the same
> size (e.g., 1, 10, 55 above) We don't want to choose classes uniformly but
> elements and again mhansen beat me to an implementation:
>
> def random_monomial_less_than_degree(n, degree):
> #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 one
> random_index = randint(0, total-1)
> #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 )
> return monomial
>
> However, an implementation without the need to explicitly construct the counts
> array would be good.
>
> With this in place one can start thinking about constructing random
> polynomials from random monomials. For this we don't have an elegant solution
> yet. We (=Steffen and me) distinguish two cases:
>
> Let #T be the number of terms requested.
>
> If $MM is the number of all possible monomials of all allowed degree <= d and
> #T < $MM/2 then we generate #T _distinct_ monomials as above and assign
> random coefficients (possibly zero). The overhead of requesting distinct
> monomials should be at most 2 because if we are looking for 1/2 of the search
> space, every second choice should be a double.
>
> If #T > $MM/2 we generate all possible monomials, pick #T and assign
> coefficients. This should be more effective for this case because we don't
> generate any doubles (but memory is more precious than cpu cycles, so we
> might have to move that barrier up a bit).
>
> Does this sound like a sensible approach?
>
> Martin
>
> --
> name: Martin Albrecht
> _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
> _www: http://www.informatik.uni-bremen.de/~malb
> _jab: [EMAIL PROTECTED]
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
