リストのためのシンプルなクラスタリングアルゴリズム

リストのためのシンプルなクラスタリングアルゴリズム 2026年5月24日 #technical #learning サブリストの反転を使用して、リストの値のクラスタリングを人間が理解しやすい方法で実験しています。つまり、普通の言葉で言うと、幼児のマグナタイルで遊んでいて、並べ替えやグループ化のパターンに気づき、それを小さな…アルゴリズム？ヒューリスティック？とにかく、見てください！参考のために作ったビデオはこちらです。 ビデオよりも言葉で説明する方が良い場合は、次のようになります。 値がb、g、o、またはrであるリストがあるとします。 初期状態：bgogbrbroorrgbgorrbggo 行うことは、末尾にある値（この場合はo）を取り、その同じ値を持つ最も近い次の値を末尾から探し、それらの間のサブリストを反転させます。 したがって、次のイテレーションは次のようになります。 bgogbrbroorrgbgooggbrr ▲ ▲ └──┬─┘ この部分が反転されました 右から2番目のoの右側にあるすべてのものを反転させました。そして、同じことを行います。今度はrのグループが末尾に来たので、次のrまでのサブリストを反転させます。 bgogbrbroorrrrbggoogbg ▲ ▲ └────┬───┘ この部分が反転されました そして、このように続きます。 bgogbrbroorrrrbggooggb （gで反転） bgogbrbroorrrrbbggoogg （bで反転） bgogbrbroorrrrbbggggoo （gで再度反転） bgogbrbrooooggggbbrrrr bgogbrbrrrrrbbggggoooo bgoooooggggbbrrrrrbrbg bgooooogggggbrbrrrrrbb bgooooogggggbrbbbrrrrr bgooooogggggbrrrrrrbbb bgooooogggggbbbbrrrrrr この時点で、rは完了したので、末尾から見て不完全な次のグループに進み、反転します。 bgooooogggggrrrrrrbbbb ▲ ▲ └────┬───┘ bがまだ不完全なので、この部分が反転されました そして通常通り続けます。 bbbbbrrrrrrgggggooooog bbbbbrrrrrrggggggooooo （最終的なクラスタ化された状態） 最も効率的ではありませんが、非常に興味深いです。各ステップで現在の最適化のみに焦点を当てるため、「貪欲」です。 類似のアイデアを調べたところ、パンケーキソートに最も近いと思われます（これはソートが中心で、グループ化ではなく、スタックが対象ですが、それ以外は多くの類似した概念を持っています）。 コード！ AIを使わずに、楽しい頭の体操として実際の関数を書きましたが、正直に言って疲れました（しばらくの間、ソートアルゴリズムをゼロから書いたことがありません）。クリーンアップには試行錯誤が必要でした。 ネストされたwhileループを使用したため、O(n^2)の時間計算量があります。最初は再帰を使ってみました（最初に考えたときはマージソートに似ているように感じたため）、この方法の方がうまくいくことがわかりました。 以下は、明確にするためのコメント付きの最終的なコードです。 function cassidyCluster(input) { // 実際には配列を入力するのが「より適切」ですが // 文字列も受け入れられるようにしています const list = typeof input === "string" ? input.split("") : [...input]; const listLength = list.length; // リストの一部を反転させるヘルパー関数 function reverse(arr, left, right) { while (left < right) { [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; } } while (true) { let right = listLength - 1; let clusterStartingIndex; let frontOfReversingSection; // 同じ要素の最も右のクラスタを取得 while (right > 0) { const target = list[right]; clusterStartingIndex = right; while ( clusterStartingIndex > 0 && list[clusterStartingIndex - 1] === target ) { clusterStartingIndex--; } frontOfReversingSection = clusterStartingIndex - 1; while ( frontOfReversingSection >= 0 && list[frontOfReversingSection] !== target ) { frontOfReversingSection--; } if (frontOfReversingSection >= 0) break; right = clusterStartingIndex - 1; } // これ以上完了すべきクラスタがない場合は終了 if (right <= 0) break; if (right < listLength - 1) { // 最も右のクラスタが「完了」したら、次に完了すべきクラスタを含むセクションを反転させる reverse(list, clusterStartingIndex, listLength - 1); } else { // ベースケース：最も右のクラスタに一致するセクションを反転させる reverse(list, frontOfReversingSection + 1, listLength - 1); } } return list; } 人間は素晴らしい これは非常に興味深い問題だと思います。なぜなら…コンピュータが解決するよりも、目の前にあるオブジェクトを使って物理的な人間がこれを解決する方がはるかに簡単だからです。コンピュータは、私たちがグループを掴んでひっくり返すようなことを簡単には理解できません。私たちの目は、目の前の状態を「O(1)で読み取る」ことができ、ピースを1つの「動き」でひっくり返すことができます。とにかく、これが非効率的で無意味だと誰かが教えてくれると確信していますが、子供たちと遊びながらこれをいじって楽しかったです。数学万歳！