.. -*- coding: utf-8; -*-

=============================
Rudin-Shapiro文字列
=============================
| 初期文字  :math:`a` , :math:`b` , :math:`c` , :math:`d`  による :math:`n` 番目のRudin-Shapiro文字列

.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/Rudin-Shapiro.js">
         </script>

          <form onsubmit="return false;" autocomplete="off">
		  <div>
		  n = <input id="n" type="int" size="64" value="0"/>
		  </div>
     	  <div>
		  a = <input id="a" type="text" size="64" value="a"/>
		  </div>
		  <div>
		  b = <input id="b" type="text" size="64" value="b"/>
          </div>
		  <div>
		  c = <input id="c" type="text" size="64" value="c"/>
          </div>
		  <div>
		  d = <input id="d" type="text" size="64" value="d"/>
          </div>
		  <div>
		  a,b → <input id="x" type="text" size="64" value="1"/>
          </div>
		  <div>
		  c,d → <input id="y" type="text" size="64" value="-1"/>
          </div>
		  </form>
		  <div style="word-wrap:break-word;"> ・RS(n) = <RS>dummy</RS> </div>
		  <div style="word-wrap:break-word;"> ・RS(n) = <RS_replace>dummy</RS_replace> </div>

| **注** ：:math:`n` を大きい数にするとおかしくなります．(入力制限で :math:`n<30` としています)
| アルゴリズムはループの方を使用．


定義
=========================================

:math:`n` 番目の **Rudin-Shapiro文字列** *(Rudin-Shapiro Word)* :math:`RS_n` を以下のような定義で生成する．

また，:math:`RS_n` は， :math:`RS_{n-1}` に対して次の規則に従った変換を行うことにより生成することもできる．
ただし， :math:`RS_0 = a` とする．

- :math:`a → ab`
- :math:`b → ac`
- :math:`c → db`
- :math:`d → dc`



性質
========================

:math:`RS_n = abacabdbabacdcac...` に対して

 - :math:`a → 1`
 - :math:`b → 1`
 - :math:`c → -1`
 - :math:`d → -1`

と置き換えるとRudin-Shapiro wordの :math:`n` 番目の項は
 
 - :math:`RS_n = (-1)^{a(n)}`　

となる．ここで :math:`a(n)`　は :math:`n`　を2進数で表した際の11の数である．

| Rudin-Shapiro wordに含まれる回文の長さは{0,1,2,3,4,5,6,7,8,10,12,14}となり15文字以上の長さの回文は出現しない.
| ( :math:`n =` 6のとき初めて14文字の回文が出現する.)


アルゴリズム集
=========================================

:math:`n` 番目のRudin-Shpiro文字列を返す
-----------------------------------------

.. literalinclude:: /Scripts/Python/Rudin-Shpiro_word.py
   :pyobject: RS


参考文献
--------
 - M.Lothaire (July 25, 2005), Applied combinatorics on words (Encyclopedia of Mathematics and its Applications), Cambridge University Press