ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 21 May 2016 21:16:37 -0500Is there a functional way to manipulate cycles extracted from a digraph?https://ask.sagemath.org/question/33425/is-there-a-functional-way-to-manipulate-cycles-extracted-from-a-digraph/ I wrote a worksheet that defines a digraph and extracts all of its simple cycles.
pr = prime_range(3600)
wief = DiGraph([pr, lambda p, q: power_mod(p, q - 1, q^2) == 1]) # could take a while!
sc = wief.all_simple_cycles()
sc.append([0, 0])
Then it uses mostly procedural code to:
1. Remove the duplicate endpoints
2. Reverse-sort the cycle
3. Group cycles by length
4. Sort the group of cycles
5. Return the first (lexicographically
earliest) cycle of each length
>
maxn = 0
for c in sc:
del c[0] # duplicate
maxn = max(maxn, len(c))
c.sort(reverse=True) # reverse lexicographic
# group by length
tbl = [[c for c in sc if len(c) == n] for n in range(1,maxn)]
n = 1
for t in tbl: # sort tuples by max element, get smallest tuple
t.sort()
print 'n=%d:'%(n),
# why can't join handle a list of integers?
print ', '.join(map(lambda m: '%s'%(m), t[0]))
n = n + 1
The worksheet is adequate - it performs step 5 correctly, but a listing of the code will be posted as the PROG paragraph of an OEIS entry. So I would **really** like to reduce the numbered steps to as few lines as possible. Are there more graceful ways to tweak the output of one function before passing it on to another?Tue, 17 May 2016 01:51:38 -0500https://ask.sagemath.org/question/33425/is-there-a-functional-way-to-manipulate-cycles-extracted-from-a-digraph/Answer by Maybeso83 for <p>I wrote a worksheet that defines a digraph and extracts all of its simple cycles. </p>
<pre><code>pr = prime_range(3600)
wief = DiGraph([pr, lambda p, q: power_mod(p, q - 1, q^2) == 1]) # could take a while!
sc = wief.all_simple_cycles()
sc.append([0, 0])
</code></pre>
<p>Then it uses mostly procedural code to: </p>
<ol>
<li>Remove the duplicate endpoints</li>
<li>Reverse-sort the cycle</li>
<li>Group cycles by length</li>
<li>Sort the group of cycles</li>
<li>Return the first (lexicographically
earliest) cycle of each length</li>
</ol>
<blockquote>
<p></p>
</blockquote>
<pre><code>maxn = 0
for c in sc:
del c[0] # duplicate
maxn = max(maxn, len(c))
c.sort(reverse=True) # reverse lexicographic
# group by length
tbl = [[c for c in sc if len(c) == n] for n in range(1,maxn)]
n = 1
for t in tbl: # sort tuples by max element, get smallest tuple
t.sort()
print 'n=%d:'%(n),
# why can't join handle a list of integers?
print ', '.join(map(lambda m: '%s'%(m), t[0]))
n = n + 1
</code></pre>
<p>The worksheet is adequate - it performs step 5 correctly, but a listing of the code will be posted as the PROG paragraph of an OEIS entry. So I would <strong>really</strong> like to reduce the numbered steps to as few lines as possible. Are there more graceful ways to tweak the output of one function before passing it on to another?</p>
https://ask.sagemath.org/question/33425/is-there-a-functional-way-to-manipulate-cycles-extracted-from-a-digraph/?answer=33503#post-id-33503With the help of a PARI programmer and OEIS regular I cleaned up my code:
wief = DiGraph([prime_range(3600), lambda p, q: power_mod(p, q-1, q^2)==1])
sc = [[0]] + [sorted(c[1:], reverse=1) for c in wief.all_simple_cycles()]
tbl = [sorted(filter(lambda c: len(c)==n, sc))[0] for n in range(1, len(sc[-1]))]
for t in tbl: print 'n=%d:'%(len(t)), ', '.join("%s"%i for i in t)
and posted it to OEIS sequence A271100 Wieferich n-tuples. I used it to increase the number of listed terms from 15 to 300. We'll probably bump that to nearly 10k soon : )
*For the community, I'd like to add mouse-over hints describing what each piece of code does but I'm a noob.
Sat, 21 May 2016 21:16:37 -0500https://ask.sagemath.org/question/33425/is-there-a-functional-way-to-manipulate-cycles-extracted-from-a-digraph/?answer=33503#post-id-33503