#16683: gray code for integer vectors and combinations
-------------------------------------+-------------------------------------
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 | 4d2136a6d0505c15c0b1af4fb4c7ea22aa4980f6
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
If I make no mistake :
With a gray code that makes you change two coordinates for each vector,
you need to do `2n^k` to enumerate the elements of `n^k`
If you just have an integer written on `k` digits and you want to go from
0000... to k-1,k-1,...,k-1 by adding 1 one it, how many changes occur ?
The leftmost coordinate is changed `n` times. The second is changed `n^2`
times. The last is changed `n^k` times. What is the total ?
{{{k+k^2+...+k^n=(1-k^n+1)/(1-k)-1}}}
Result :
{{{
sage: 2*n^k # number of changes with a gray code
1620000
sage: (1-n^(k+1))/(1-n)-1 # number of changes with addition
837930
}}}
Thus if you really care about those changes, may you should build a
function which outputs the changes that must be performed at each run,
based on stupid addition ? Or did I make a mistake somewhere ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/16683#comment:8>
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.
