HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

A simple clustering algorithm for lists (cassidoo.co)

9 pointsby nreece2 コメント

要約

この記事では、おもちゃのタイルを並べ替えることから着想を得た、リストの値のクラスタリング手法を紹介しています。リストの末尾にある要素と同じ要素を見つけ、それらの間のサブリストを反転させるという操作を繰り返すことで、要素をグループ化します。この「貪欲」なアプローチは、物理的な操作の直感性をコンピュータ処理に落とし込む試みであり、O(n^2)の計算量を持つJavaScriptコードも提供されています。

全文翻訳

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

私は、サブリストの反転を使って、人間が理解しやすい方法でリストの値をクラスタリングする実験をしてきました。つまり、普通の言葉で言うと、子供のMagna-Tilesで遊んでいて、並べ替えやグループ化のパターンに気づき、それをちょっとした…アルゴリズム?ヒューリスティック?とにかく、見てください!

参考のために作った動画はこちらです。

言葉よりも動画の方が良いという方のために:値が 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なしで実際の関数を作成しました。正直、疲れました(ソートアルゴリズムを一から書くのは久しぶりです)。きれいに整理するのに試行錯誤が必要でした。計算量は O(n^2) です(ネストしたwhileループを使用したため)。最初は再帰を使ってみました(最初に考えたときはマージソートに似ているように感じたので)、しかしこの方法の方がうまく機能することがわかりました。

以下は、明確にするためのコメント付きの最終的なコードです。

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回の「移動」でひっくり返すことができます。

とにかく、これは非効率で無意味だと誰かが教えてくれると確信しています。なぜなら、それはそういう側面もあるからです…しかし、子供たちと遊びながらこれをいじって、とても楽しい時間を過ごしました。数学、万歳!