ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 08 Aug 2019 10:54:34 -0500The shortest string containing all given substringshttp://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/I found a problem from https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=tuet . An English translation goes like this:
A person wants to learn playing tuba. His neigbours get angry for the noise so he tries to find a song that contains as few tunes as possible that he is able to play all four or less tune combinations. The tunes are c, d, e, f, g, a, and h. Output the minimal song.
I tried a code from https://artofproblemsolving.com/community/c163h1889399_shortest_string_containing_all_substrings .
def de_bruijn(k, n):
"""
de Bruijn sequence for alphabet k
and subsequences of length n.
"""
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
seq = de_bruijn("cdefgah", 4)
print(seq)
But the validator on the site says that hccc is missing.
So, how can I use Sagemath to solve the problem that if a set contains letters a, c, d, e, f, g, h, how to find the shortest string containing all one to four letter long substrings?Thu, 08 Aug 2019 08:48:23 -0500http://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/Comment by John Palmieri for <p>I found a problem from <a href="https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=tuet">https://www.ohjelmointiputka.net/post...</a> . An English translation goes like this:</p>
<p>A person wants to learn playing tuba. His neigbours get angry for the noise so he tries to find a song that contains as few tunes as possible that he is able to play all four or less tune combinations. The tunes are c, d, e, f, g, a, and h. Output the minimal song.</p>
<p>I tried a code from <a href="https://artofproblemsolving.com/community/c163h1889399_shortest_string_containing_all_substrings">https://artofproblemsolving.com/commu...</a> . </p>
<pre><code>def de_bruijn(k, n):
"""
de Bruijn sequence for alphabet k
and subsequences of length n.
"""
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
seq = de_bruijn("cdefgah", 4)
print(seq)
</code></pre>
<p>But the validator on the site says that hccc is missing.</p>
<p>So, how can I use Sagemath to solve the problem that if a set contains letters a, c, d, e, f, g, h, how to find the shortest string containing all one to four letter long substrings?</p>
http://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/?comment=47441#post-id-47441If you want a Sagemath solution, there is http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/debruijn_sequence.html. You would have to translate the numbers 1, 2, ..., 7 to the letters a, c, d, ... h, but that should be easy.Thu, 08 Aug 2019 10:54:34 -0500http://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/?comment=47441#post-id-47441Answer by nbruin for <p>I found a problem from <a href="https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=tuet">https://www.ohjelmointiputka.net/post...</a> . An English translation goes like this:</p>
<p>A person wants to learn playing tuba. His neigbours get angry for the noise so he tries to find a song that contains as few tunes as possible that he is able to play all four or less tune combinations. The tunes are c, d, e, f, g, a, and h. Output the minimal song.</p>
<p>I tried a code from <a href="https://artofproblemsolving.com/community/c163h1889399_shortest_string_containing_all_substrings">https://artofproblemsolving.com/commu...</a> . </p>
<pre><code>def de_bruijn(k, n):
"""
de Bruijn sequence for alphabet k
and subsequences of length n.
"""
alphabet = k
k = len(k)
a = [0] * k * n
sequence = []
def db(t, p):
if t > n:
if n % p == 0:
sequence.extend(a[1:p + 1])
else:
a[t] = a[t - p]
db(t + 1, p)
for j in range(a[t - p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return "".join(alphabet[i] for i in sequence)
seq = de_bruijn("cdefgah", 4)
print(seq)
</code></pre>
<p>But the validator on the site says that hccc is missing.</p>
<p>So, how can I use Sagemath to solve the problem that if a set contains letters a, c, d, e, f, g, h, how to find the shortest string containing all one to four letter long substrings?</p>
http://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/?answer=47440#post-id-47440The program doesn't use any sage-specific functionality, and it doesn't have to. You can just use any correct python implementation. The routine presented seems like a verbatim copy of the one on https://en.wikipedia.org/wiki/De_Bruijn_sequence . Note that the definition of a "de bruijn sequence" includes it's a *cyclic* sequence. So you should be appending the head of the sequence to the tail:
"hccc" in seq+seq[:3]Thu, 08 Aug 2019 10:34:53 -0500http://ask.sagemath.org/question/47438/the-shortest-string-containing-all-given-substrings/?answer=47440#post-id-47440