Generate valid Fibonacci tilings
APL (Dyalog Unicode), 43 bytes
(1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+
Try it online!
This uses the alternative formulation (actually the first one) shown in the linked paper: the closest integer staircase to the line \$y = x/\phi\$, where \$\phi\$ is the golden ratio \$\frac{\sqrt5+1}{2}\$.
Given the initial vertical offset from the line \$h\$ (which can be positive or negative), the next term (one of LS) can be determined by the following rule:
- If \$h<0\$ (below the line), \$h←h+1\$ and emit
S. - Otherwise (over the line), \$h←h-(\phi-1)\$ and emit
L.
Since \$h-(\phi-1) = h+1-\phi\$, we can always increment and take modulo \$\phi\$ of it. Then the condition \$h<0\$ changes to \$h<\phi-1\$, but it doesn't affect the resulting sequence of terms.
Then the problem becomes to sample enough values for initial \$h\$ so that we can get all possible sequences of SL for any given length \$n\$. I choose \$2^{n+1}\$ points uniformly spaced over the interval \$[0,\phi)\$, which works for small \$n\$, and the gap size reduces faster than that induced by the collection of lines \$y=x/\phi+c\$, each passing through some lattice point inside \$0 \le x \le n\$.
Finally, I determine the actual SL terms by checking each consecutive pair: S if left < right, L otherwise, and take unique sequences.
(1+∘÷⍣=1){'LS'[∪2</⍺|(⍺×(⍳÷⊢)2*⍵)∘.+⍳⍵]}1∘+ ⍝ Input: n
(1+∘÷⍣=1){...}1∘+ ⍝ Pass n+1 and phi to the inner dfn...
⍳⍵ ⍝ Range 0..n
∘.+ ⍝ Outer product by addition...
(⍺×(⍳÷⊢)2*⍵) ⍝ 2^(n+1) uniformly separated numbers in [0,phi)
⍺| ⍝ Modulo phi
2</ ⍝ Pairwise comparison in row direction
⍝ (1 if right is higher, 0 otherwise)
∪ ⍝ Take unique rows
'LS'[...] ⍝ Map 0, 1 to L, S
CJam, 70 62 59 bytes
Qali{_'L:Xf+\'S:Yf++}*{{_X2*/Xf-Yf/Xf*Y*}h]N*_X3*#\Y2*#=},p
Reads from STDIN. Try it online.
Example run
$ cjam tilings.cjam <<< 5
["LLSLL" "SLSLL" "SLLSL" "LSLSL" "LSLLS" "LLSLS"]
How it works
The idea is to push all strings of L's and S's of the proper length, successively apply the transformation to each until the result is an empty string, concatenate the sequences of strings and search for the forbidden substrings.
Qa " Push R := [ '' ]. ";
li{ " Do the following int(input()) times: ";
_'L:Xf+ " Append (X := 'L') to a copy of all strings in R. ";
\'S:Yf+ " Append (Y := 'S') to all original strings in R. ";
+ " Concatenate the arrays into R. ";
}* " R now contains all strings of L's and S's of length int(input()). ";
{ " For each S ∊ R: ";
{ " ";
_ " Push a copy of S. ";
X2*/ " Split S at 'LL'. ";
Xf- " Remove 'L' from the chunks. ";
Yf/ " Split the chunks at 'S'. ";
Xf* " Join the chunks, separating by 'L'. ";
Y* " Join, separating by 'S'. ";
}h " If the resulting string is non-empty, repeat. ";
]N* " Join the array of resulting strings from S to '', separating by linefeeds. ";
_X3*# " Push the index of 'LLL' a copy in the resulting string (-1 if not present). ";
\Y2*# " Push the index of 'SS' in the original string (-1 if not present). ";
= " Check if the indexes are equal; this happens if and only if both are -1. ";
}, " Filter: Keep S in R if and only if = pushed 1. ";
p " Print a string representation of R. ";
GolfScript (86 bytes)
~:|'LS'1/\{{.{1&!'LLS'2/=}%'SS'/'SLS'*[.(1&{'LS'\+}*]{.)1&{'SL'+}*}/}%.&}*['']+{,|=},p
This is an inflationary approach: it starts with L and S and expands them using the rules LL -> SLS, L -> S, S -> LL, and leading or trailing S can have an L added at the word boundary.
Online demo