#16683: fast gray code for integer vectors
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/16683 | 9d90d4873303b1e91ef6bbcaf3fe7250dff38d3c
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hellooooo !!
Sorry for being unpleasant, but I've got two design questions `:-P`
1) I guess that you wrote all this as a class because you need a malloc
and that you can't call "free" whenever you need in an iterator function.
This being said, do you think that using a `int *` is much better than a
`cdef list` in this case ?
2) Also, I wonder about the need of a gray iterator in the case of a
cartesian product. If you do it naively (let's say like a addition in base
50 if you compute the cartesian product of k sets of size 50) then in
49/50 of the cases you will only do a +1 on the last element, and nothing
else. And in 1/50*49/50 you will only need to change 2 elements. And in
(1/50)^2(49/50) you will need to change 3.. I mean: the normal algorithm
does not seem that far from the performances of a gray iterator. So you
probably would not waste much if you do the normal operations of addition,
and only update the coordinates of the current vector which changed. Most
of the time, that will be very very few.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/16683#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
