13
$\begingroup$

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.

$\endgroup$

3 Answers 3

13
$\begingroup$

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}];
$\endgroup$
8
  • $\begingroup$ What if I just wanted a random sequence of $L$ and $S$? $\endgroup$ Sep 16, 2018 at 15:59
  • $\begingroup$ 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]. $\endgroup$ Sep 16, 2018 at 16:02
  • $\begingroup$ Great, thank you. $\endgroup$ Sep 16, 2018 at 16:04
  • 2
    $\begingroup$ FYI I thanks you on Physcs SE where I used your code, physics.stackexchange.com/questions/427330/…. Thanks again. $\endgroup$ Sep 16, 2018 at 16:44
  • 2
    $\begingroup$ If the user were only interested in the twentieth iterate, they could use {20} instead of 20. $\endgroup$
    – Carl Woll
    Sep 16, 2018 at 18:39
13
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.