2016/07/31

[038] 続・文字の並べ替えと回文


内科医・眼科医、たいがいが葉ニンニク歓待にクタクタ。

[ないかいがんかいたいがいがはにんにくかんたいにくたくた](非回文)

上記の文はまったく回文になっていません。しかし回文っぽい怪文感は漂っている。さてこの文はいったい何でしょう。というのが以下の記事を読むと明らかになります。

前回のおさらい


前回の記事では、回文をはじめとするいろいろな言葉遊びを、文字の並べ替えという観点から統一的に捉える方法について書きました。要旨をざっくりまとめると、
  • 文字の並べ替えの仕方 t を1つ決めると、その並べ替えで変わらない文字列(t(x)=xとなるx)を探す言葉遊びが得られる。回文や畳文や継母聞き耳などがその例になっている。
という話でした。 たとえば文字の並べ替えとして、次の p をとると


この並べ替えで変わらない文は回文だ、という感じです。

並べ替えの繰り返し回数


前回挙げた並べ替えの例は、すべて、2回続けて行うと元に戻るものばかりでした。たとえば上の p だと、
p(らーめんたべたい)=いたべたんめーら
ですが、これにもう一度 p を施すと
p(いたべたんめーら)=らーめんたべたい
となって元に戻ります。しかしもちろん、2回行うと元に戻る並べ替えでなくても上記の言葉遊び生成メソッドは通用します。たとえば次の並べ替え s を考えてみましょう。


文字列を3等分して、最後の1つを先頭に移動させる、という並べ替えです。この s で変わらない文字列は「3畳文」とよばれています。たとえば
s(きたいきたいきたい)=きたいきたいきたい
なので、"きたいきたいきたい"(北行きたい機体)は3畳文です。

回文を定義する p などとは違って、この s は3回やらないと元に戻りません。このことによって、3畳文は、回文などよりも作るのが難しくなっています。というのは、ある文字列が s で変わらないということは、どの文字も、s で移った先の文字と一致しているだけではなくて、s をさらにもう1度施して移った先の文字とも一致している必要があるからです。それぞれの文字について一致する文字の個数が、3畳文は3個、回文は2個(中央の1字が例外で1個)となっており、3畳文のほうが制約がきつくて作りにくい、というわけです。

この「元に戻る回数」を調べることが大事になる言葉遊びを、以下に紹介します。

縦横文


縦横文というのは、縦書きにしても横書きにしても同じになる文字列のことです。(と、よく知られた名前であるかのように言っていますが、いい名前がなさそうだったので、この記事では勝手にそう呼ぶことにします。)たとえば、
かんきせんがただきたないせだいだ(換気扇がただ汚い世代だ)
というよく分からない16文字の文字列は縦横文です。4×4に並べると
かんきせ
んがただ
きたない
せだいだ
となり、左上から右方向へ読んでも下方向へ読んでも同じになるからです。(前回ちらっと書いた「SATOR陣」というのは、縦横文でもあるような回文のことです。)

この言葉遊びも、文字列の並べ替えで定義することが可能です。この場合の並べ替えは、文字列を横1列に書くとわかりにくいのですが、文字を四角形に横書きしてから考えると一目瞭然です。16文字を4×4に並べる縦横文は、次の「縦書きを横書きに直す」並べ替えで変わらない文字列だと言えます。


この並べ替えは、何回やると元に戻るでしょうか。答えは回文と同じで「2回」です。4×4の盤面を、対角線にそってひっくり返しているだけなので、2度やると元に戻るのは当然でしょう。2回なので、制約のきつさは、回文と同程度であると考えられます。

「元に戻る回数」が大事になるのはここからです。

縦横文(長方形版)


縦横文は、正方形でなく、長方形でも考えられるはずです。3×4でやってみましょう。つまり、12字の文で、1行4字で横書きにしても、1行3字で縦書きしても、同じになるものです。この場合、文字の並べ替えとしては次のものを考えることになります。


正方形が長方形になった途端、文字の並べ替えの仕方が非常にややこしくなることがわかります。たとえばBは元々Dがあった位置へ移動していますが、そのDはJの位置へ移動しており、JはFへ、FはEへ、となっています。矢印で図示すると、次のとおりです。


左上と右下の文字は移動しませんが、他の文字はあちこちを一見ランダムに巡って、5回めで元の位置へ戻ってきます。5回! したがってこの3×4縦横文はとても作りにくいです。たとえば
浮いたいい板叩いたよ
とか……
ういたい
いいたた
たいたよ
うーん。

もっとひどいケースもあります。3×6でやってみると、文字の並べ替えの様子は次のようになります。


左上と右下以外は、盤面全体を満遍なく廻ったあと、16回め!で元の位置に戻ります。だから、3×6縦横文を作ろうと思っても
良いいいいいいいいいいいいいいいいね!
みたいになってしまいますな。誰か3×6縦横文の傑作できたら教えてください(無理)。

3×4だと5回、3×6だと16回、ということは、長方形が大きくなるほど複雑になっていきそうなのですが、実はそうでもないのです。縦横サイズと、元に戻るのにかかる回数を表にしたものが次です。


太字の数字が盤面の縦横サイズで、行と列の交わるところに、戻ってくる回数が書き込まれています。色をつけてあるところは、回数が5回以下のところです。3×6だと16回なのに、3×7だと4回に減り、3×9ではなんと3回です。この3×9はそこそこお手頃なのでは、と思いまして、作ってみたのが、記事の冒頭にある謎の文章「内科医・眼科医、たいがいが葉ニンニク歓待にクタクタ」でした。

ないかいがんかいた
いがいがはにんにく
かんたいにくたくた

興味ある方はぜひ上記の表で気になる大きさの縦横文を作ってみてください。13×21の4回のとか、いいんじゃないでしょうかねー(無茶ぶり)。

次回に続きます!



おまけ:数学的に言うと


縦横文を定義する並べ替えは、数学的に興味深いものなので、数学がわかるひと向けに簡単に説明します。

縦mマス、横nマスの盤面に、長さm×nの文字列
a(0) a(1) a(2) ... a(mn-1)
を横書きし、これを縦書きだと思って左上から下方向に読んだものを
b(0) b(1) b(2) ... b(mn-1)
とします。次の図はm=3、n=4の場合です。b(0)=a(0), b(1)=a(4), b(2)=a(8), ……などとなっています。


この b は、a を用いて次のように簡潔に表せます。
b(i)=a(i×n (mod mn-1))
つまり、カッコの中に入るのは、「iをn倍して、mn-1で割った余り」です。ただし i=mn-1(盤面右下の、最後の文字)のときは例外で、b(mn-1)=a(mn-1)となります。上に図示したm=3、n=4の例を見ると、右のカッコ内の数を4倍して11(=3×4-1)で割った余りが、左の数になっていることがわかると思います。

この並べ替えを繰り返すたびに、カッコの中の数が(mod mn-1で) n 倍されていきます。したがって、並べ替えを繰り返していって元に戻る回数というのは、nj=1 (mod mn-1)となる最小の j にほかなりません。上記の表は、この j を計算して書き並べたものです。

0 件のコメント:

コメントを投稿