# Generating a pattern from user-defined rules

I want to generate a list of $L$ and $S$ according to the following rule:
upon each iteration, replace

• $S \rightarrow L$
• $L \rightarrow LS$

Such that, starting with $L$:

## $L \rightarrow LS \rightarrow LSL \rightarrow LSLLS \rightarrow LSLLSLSL \rightarrow LSLLSLSLLSLLS \rightarrow \dots$

How can I automate this with Mathematica? I just want to specify the starting letter and the number of iteration and I'd want it to spit out the final result.

For the 5th iterate:

Nest[
Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
{L},
5
]


{L, S, L, L, S, L, S, L, L, S, L, L, S}

And for the list of first 5 iterates:

NestList[
Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
{L},
5
]


{{L}, {L, S}, {L, S, L}, {L, S, L, L, S}, {L, S, L, L, S, L, S, L}, {L, S, L, L, S, L, S, L, L, S, L, L, S}}

Edit:

SubstitutionSystem operates on strings instead. It is a bit faster because it is specifically designed for Lindenmayer systems:

L = "L";
S = "S";
a = StringJoin /@ NestList[
Replace[#, {L -> Sequence[L, S], S -> Sequence[L]}, {1}] &,
{L},
20
]; // AbsoluteTiming // First
b = SubstitutionSystem[{"L" -> "LS", "S" -> "L"}, "L", 20]; // AbsoluteTiming // First

a == b


0.004506

0.001265

True

PS.: As Carl Woll pointed out, the following will return only the 20th iterate.

c = SubstitutionSystem[{"L" -> "LS", "S" -> "L"}, "L", {20}];

• What if I just wanted a random sequence of $L$ and $S$? Sep 16, 2018 at 15:59
• Then you can use RandomChoice: RandomChoice[{L, S}, {10000}] will generate a list of 10000 random letter at once (uniformly distributed). You can also prescribe probabilities for each letter, e.g. RandomChoice[{0.1, 0.9} -> {L, S}, 10000]. Sep 16, 2018 at 16:02
• Great, thank you. Sep 16, 2018 at 16:04
• FYI I thanks you on Physcs SE where I used your code, physics.stackexchange.com/questions/427330/…. Thanks again. Sep 16, 2018 at 16:44
• If the user were only interested in the twentieth iterate, they could use {20} instead of 20. Sep 16, 2018 at 18:39

You may use ReplaceRepeatedwith its MaxIterationsoption.

ReplaceRepeated[{L}, {L -> Sequence[L, S], S -> Sequence[L]},
MaxIterations -> 5]

{L, S, L, L, S, L, S, L, L, S, L, L, S}


Hope this helps.

A recursive method:

ClearAll[f]
f[L] = Sequence[L, S];
f[S] = L;
f[a__, b_] := f[a, b] = Sequence[f @ a, f @ b]

List @ Nest[f, L, 7]


{L, S, L, L, S, L, S, L, L, S, L, L, S, L, S, L, L, S, L, S, L, L, S, L, L, S, L, S, L, L, S, L, L, S}