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$
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$
  • $\begingroup$ What if I just wanted a random sequence of $L$ and $S$? $\endgroup$ – SuperCiocia Sep 16 '18 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$ – Henrik Schumacher Sep 16 '18 at 16:02
  • $\begingroup$ Great, thank you. $\endgroup$ – SuperCiocia Sep 16 '18 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$ – SuperCiocia Sep 16 '18 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 '18 at 18:39
12
$\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, privacy policy and cookie policy

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