13世紀の列挙アルゴリズム、700年間無視される

Aboulafia's Tserouf · パート1/4 次へ: Bill Gatesに触発されたエレガントな定式化 → これは、私がカバラ思想家アブラハム・アブーラフィア（1240年～1291年以降）の著作を研究中に発見した発見についてのシリーズ記事の最初のものです。 Tseroufは文字を置換するカバラの技法であり、単純な数学的用語で言えば、n文字の単語の全ての順列の列挙です。 文脈 「Or ha-Sekhel」（「知性の光」）の中で、アブーラフィアはn文字の単語の可能な全ての配置を体系的に列挙する方法を処方しています。この方法は、精神的な実践の枠組みの中で考案されていますが、驚くほど厳密な数学的構造を持っています。 3文字の単語について、アブーラフィアはTserouf、つまり6つの順列全ての順序を明示的に示しています。 単語は、最初の文字によって3つのグループに分けられます。まず、aで始まる単語。次に、bで始まる単語。最後に、cで始まる単語です。 3文字のための2つの規則 アブーラフィアは、3文字のTseroufのための2つの規則を明示的に述べています。 規則1 — ミラー。全体のシーケンスは、開始した場所の逆順で終わらなければなりません。アブーラフィアはこれを平易に述べています。「最後の発話は最初の発話の逆である。」最初の単語はabcであり、最後はcba、つまり最初から最後まで反転したものでなければなりません。 規則2 — 頭を保持する。最初の文字を、それが手放されるまでできるだけ長く保持します。aで始まる全ての単語を使い果たし、次にbで始まる全ての単語、次にcで始まる単語を使い果たします。頭は、そうする必要があるまで変わりません。 これらの2つの規則は、3文字の順序全体をほぼ強制するのに十分です。しかし、1つのケースが私を悩ませました。なぜbcaがbacの前に来るのか、その逆ではないのか？ 2つの規則のどれも、それを強制するようには見えません。その小さな疑問が、この発見全体のエンジンです。時には単純な疑問が貴重であることが判明します。私は数ヶ月間それを手放すことができませんでした。そして、結果として、それを追いかけることがこのシリーズの全てにつながったのです。 nからn + 1へ：車輪を回す 3文字の順序から4文字の順序にどうやって移行するのでしょうか？ アブーラフィアはもう1つの規則を与えており、それが全体の中核です。「最初に戻って、最初の文字を単語の最後に送る。」つまり、単語を1ノッチ回転させます。abcdはbcdaになり、cdabになり、dabcになります。4つの回転、4つの頭、4つのグループ。そして、各グループの中で、残りの文字に全く同じ方法を適用します。 各行は、単語の1つの回転によってヘッダーが付けられ、各行は残された文字に適用される3文字順序の完全なコピーです。 統一された規則 アブーラフィアの天才を明らかにするのはこれです。全体の手順 — 3文字、4文字、10文字、任意の数 — は、あらゆるスケールで繰り返し適用される1つの操作によって支配されています：最初の文字を最後に送る。それがトップレベルで次のグループにあなたを連れて行く単一の回転です。それは、残された文字に適用され、各グループを1レベル下で構築するのと同じ回転です。そして再び、その下のレベルで。単一のジェスチャーが、順列の完全なネストされた階層を歩きます。単語が長くなるにつれて方法はより複雑になるのではなく、単に短いサブワードに同じ移動を繰り返し適用するだけです。 これはコンピュータサイエンティストが再帰アルゴリズムと呼ぶものであり、美しく経済的なものです。規則は述べるのが些細ですが、それは全てのn!の配置を、それぞれ正確に一度だけ生成し、あなたを開始点に戻します。 アブーラフィアは、章の最初の行で全体に名前を付けています。 この規則は理解しやすいです。そして、私たちが把握できる終わりはありませんが、それは必然的に終わりを持っています。3つの節、3つの瞬間：規則は単純です。それが展開するものは、私たちが心に留めておくことができるものを超えています。そしてそれでも、その歩みは有限です — それは閉じ、必然的に終わりを持っています。 そうした人々は他にいない 私がその時知らなかったのは、それにどれほど多くのことがかかっていたかということです。17世紀まで、アブーラフィア以外に順列の順序を与えた人はいませんでした。他の全ての伝統 — 他のカバラ思想家 — は、単にそれらをテーブルにリストアップしていました。bcaとbacの間のその小さな選択は、世界で唯一の体系的な方法の目に見える先端でした。 1つの顕著な歴史的並行があります。順列を網羅する規則ベースの方法を独立して発明した唯一の他の人々は、17世紀のイギリスのベルリンガーでした。ベルリンガーは鐘楼でその順序を見つけました。アブーラフィアはそれを精神的な実践で見つけました。異なる世界、同じ目標：全てを網羅し、何も漏らさず、何も繰り返さない順列の全空間をたどる方法。そしてアブーラフィアは13世紀に行いました — ベルリンガーの300年前、そしてコンピュータサイエンスの700年前です。 これがどこへ行くのか したがって、アブーラフィアは順列のための本物の再帰アルゴリズムを与えました。それだけでも素晴らしい歴史的注記となるでしょう。しかし、さらに多くのことがあります。彼の正確な順序は、1984年に数学者Shimon Zaksによって発表されたアルゴリズムと一致することが判明しました。これは全く異なる扉から到達され、若いビル・ゲイツが彼の唯一の科学論文で研究した動きに基づいています。それが次の記事です。