[心得] 自我描述數列與String pattern

[jurian0101 (Hysterisis)]

自我描述數列是這玩意兒
http://zh.wikipedia.org/wiki/%E5%A4%96%E8%A7%80%E6%95%B8%E5%88%97

= 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211  (說明見上)

[實作1]

LookSay[str_String] := StringJoin @@
  StringCases[str, p : ((x_(*?DigitQ*)) .. ~~ (x_ | "")) :>
     ToString@StringLength[p] <> StringTake[p, {1}]];

- -

NestList[LookSay, "1", 10]

=> {"1", "11", "21", "1211", "111221", "312211", "13112221",
"1113213211", "31131211131221", "13211311123113112211",
"11131221133112132113212221"}

- -

說明: 函數核心部分在於
    StringCases[str, ((x_(*?DigitQ*)) .. ~~ (x_ | ""))]

它的作用是把  "11223aaaab" 拆成 {"11", "22", "3", "aaaa", "b"}

若把(*?DigitQ*)的註解拿掉，則忽略掉字母。

叫做核心因為string pattern我最不熟，這部分改了最久XD

其他部分只是在做 "111" -> "3個1" -> "31" 這件事而已，是個拼拼湊湊。

- * - *

ListPlot[Log[StringLength /@ NestList[LookSay, "1", 40]],
 PlotLabel -> "Log[length[LS[n]]]"]

(*數列的長度依指數增長的圖示，原理的說明見wiki跟下*)
http://www.njohnston.ca/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.213.88
→ jurian0101:哭哭，比OEIS A005150給的代碼慢三倍。
推 sunev:為什麼要用String?
→ sunev:f[n_Integer /; n > 0] := FromDigits@Flatten@
→ sunev:({Length[#], First[#1]} & /@ Split@IntegerDigits@n)
推 sunev:如果把最前面和最後面的FromDigits和IntegerDigits拿掉
→ sunev:可以再快一點。
→ jurian0101:因為string pattern這塊一直不敢碰它，這次當作練習
→ jurian0101:效率的話OEIS A005150底下給的程式碼看來落落長卻莫名
→ jurian0101:地快，我/你/他的代碼跑第50個數，需時約3:2:1
→ jurian0101:又我不太會監測Memory usage，不知哪個較省
推 sunev:突然發現我的f和他的第二個寫法一模一樣。
→ sunev:但是如果把FromDigits和IntegerDigits拿掉就比第一個快了。
→ sunev:g[n_] := Flatten[({Length[#1], First[#1]} &) /@ Split[n]
→ sunev:NestList[g, {1}, 50]; // Timing
→ jurian0101:XD 現在你的寫法跟Steven Wolfram一模一樣，在說明文件
→ jurian0101:Split精巧範例的第二個，同時也在NKS 905頁上
推 sunev:XD