Lyndon word: Difference between revisions
m
→{{header|EasyLang}}
imported>CosmiaNebula (clearer language) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 23:
# Since the last symbol is 0, it is not the final symbol.
# Increment the last symbol to obtain <math>x = 00111\;01 </math>.
=={{header|EasyLang}}==
{{trans|Python}}
<syntaxhighlight>
func$ nextword n w$ alpha$ .
alpha$[] = strchars alpha$
while len x$ < n
x$ &= w$
.
x$[] = strchars substr x$ 1 n
while len x$[] > 0 and x$[len x$[]] = alpha$[len alpha$[]]
len x$[] -1
.
lx = len x$[]
if lx > 0
repeat
i += 1
until alpha$[i] = x$[lx]
.
x$[lx] = alpha$[i + 1]
.
return strjoin x$[]
.
proc lyndon n alpha$ . .
w$ = substr alpha$ 1 1
while len w$ <= n and len w$ > 0
print w$
w$ = nextword n w$ alpha$
.
.
lyndon 5 "01"
</syntaxhighlight>
=={{header|jq}}==
{{Works with|jq}}
'''Works with gojq, the Go implementation of jq'''
This entry defines a filter, `lyndon`, for finding the Lyndon word of the input string, if any, but is otherwise adapted from the [[#Wren|Wren]]
entry.
<syntaxhighlight lang="jq">
# Generic stream-oriented min function
# Assume the stream s is not empty and does contain null
def min(s):
reduce s as $x (null; if . == null then $x elif . < $x then . else $x end);
# Input: a string
# Assume 0 <= $n <= length
def rotate($n):
.[$n:] + .[:$n];
# Emit the Lyndon word corresponding to the input string, else empty.
def lyndon:
def circular:
. as $in
| any( range(1; length/2 + 1); . as $n | $in | rotate($n) == .) ;
if circular then empty
else min(range(0;length) as $i | rotate($i))
end;
# Input: a Lyndon word
# Output: the next Lyndon word relative to $alphabet
def nextWord($n; $alphabet):
def a($i): $alphabet[$i:$i+1];
((($n/length)|floor + 1) * .)[:$n]
| until (. == "" or .[-1:] != $alphabet[-1:]; .[:-1])
| if . == "" then .
else .[-1:] as $lastChar
| ($alphabet|index($lastChar) + 1) as $nextCharIndex
| .[0:-1] + a($nextCharIndex)
end ;
def lyndon_words($n):
. as $alphabet
| .[:1]
| while ( length <= $n and . != "";
nextWord($n; $alphabet) ) ;
"01" | lyndon_words(5)
</syntaxhighlight>
{{output}}
As for [[#Wren|Wren]].
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight lang="julia">function nextword(n, w, alphabet)
x = (w ^ ((n ÷ length(w)) + 1))[begin:n]
while x != "" && x[end] == alphabet[end]
x = x[begin:end-1]
end
if x != ""
last_char = x[end]
next_char_index = something(findfirst(==(last_char), alphabet), 0) + 1
x = x[begin:end-1] * alphabet[next_char_index]
end
return x
end
function generate_lyndon_words(n, alphabet)
lwords = String[]
w = string(alphabet[begin])
while length(w) <= n
push!(lwords, w)
w = nextword(n, w, alphabet)
w == "" && break
end
return lwords
end
const lyndon_words = generate_lyndon_words(5, "01")
foreach(println, lyndon_words)
</syntaxhighlight>{{out}} Same as Python example.
== {{header|Phix}} ==
Line 103 ⟶ 216:
</syntaxhighlight>
=={{header|Raku}}==
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20240211 Raku programming solution
sub nextword($n, $w, $alphabet) {
my $x = ($w x ($n div $w.chars + 1)).substr(0, $n);
while $x.Bool && $x.substr(*-1) eq $alphabet.substr(*-1) {
$x.substr-rw(*-1) = ''
}
if $x.Bool {
my $next_char_index = ($alphabet.index($x.substr(*-1)) // 0) + 1;
$x.substr-rw(*-1, 1) = $alphabet.substr($next_char_index, 1);
}
return $x;
}
.say for sub ($n, $alphabet) {
my $w = $alphabet.substr(0, 1);
return gather while $w.chars <= $n {
take $w;
last unless $w = nextword($n, $w, $alphabet);
}
}(5, '01');</syntaxhighlight>
{{out}} Same as Julia example.
You may [https://ato.pxeger.com/run?1=fVLLToQwFE1c8hVnQQaqwMDCxARn449MOlKEDBZti2Vi-BI3s9Cf8mtsedSMjpLQEO49j3t6394F3XfH40enyvjm84LIbgfOeqVbUYQ-j-Br89LmqaI7pghePQCPB_g9Ngh9jd6cHEX9YjqT-4oKiStkhCSGSSoRpgbOSW5huqobZpDJXds2WK3s59x1GWcE7Plb6aQwiprH9cdCT5UNgsAWB3vUpSNfENapHWdrnW1rXrAeo3GnM_4LT50QrNdIiR0k_0M6wqj-y-9PNduXO4eCqU5wQ5Z7g-clkh5QtgI29CnsM0HrczKp450pH6iqmFgiXm7i1kC5C0PRva0tIzVUKnS8YVJOKv_c-zzCEF5HCNIsIPm0MfPiLAv0BQ Attempt This Online!]
=={{header|RPL}}==
| |||