A simple clustering algorithm for lists

I’ve been experimenting with a human-friendly way to cluster list values using reversals of sub-lists. Or, in normal human words: I was playing with my toddler’s Magna-Tiles and got into a pattern with how I was sorting and grouping them, and turned it into a little… algorithm? Heuristic? Anyway, look!

Here’s a video I made for reference:

But if you prefer words over video: Let’s say you have a list where node values can be b, g, o, or r.

Initial state:bgogbrbroorrgbgorrbggo

What you do is you take the value that’s at the end (in this case o), and you find the next value closest to the end with that same value, and you reverse the sub-list between them. So, the next iteration would be:

bgogbrbroorrgbgooggbrr
                └──┬─┘
                this part was reversed

We reversed everything to the right of the second o from the right.

And then, you do the same thing, now that r group is at the end, you reverse the sub-list to the next r:

bgogbrbroorrrrbggoogbg
            └────┬───┘
            this part was reversed

And so on:

bgogbrbroorrrrbggooggb (reverse on the g)
bgogbrbroorrrrbbggoogg (reverse on the b)
bgogbrbroorrrrbbggggoo (reverse on the g again)
bgogbrbrooooggggbbrrrr
bgogbrbrrrrrbbggggoooo
bgoooooggggbbrrrrrbrbg
bgooooogggggbrbrrrrrbb
bgooooogggggbrbbbrrrrr
bgooooogggggbrrrrrrbbb
bgooooogggggbbbbrrrrrr

And at this point, because the rs are done, you’d go to the next group that is incomplete from the right, and reverse:

bgooooogggggrrrrrrbbbb
            └────┬───┘
            this part was reversed,
            because b is still incomplete

Then continue normally:

bbbbbrrrrrrgggggooooog
bbbbbrrrrrrggggggooooo (final, clustered state)

It’s not the most efficient, but it’s very interesting. It’s “greedy” because it focuses on just the current optimizations at each step. I tried looking up similar ideas and I think it is closest to pancake sort (which is more around sorting, not grouping, and focused on a stack rather than a list, but otherwise has a lot of other similar concepts).

Code!

I wrote an actual function for this without AI as a fun little brain exercise and it was exhausting, I admit (I haven’t written any sort of sorting algorithm from scratch in a minute). It took me some trial and error to clean up. It’s got O(n^2) time complexity (because I used nested while loops). I tried it with recursion at first (because it felt like it could be similar to merge sort when I was first noodling on it), and found that this way worked better.

Here’s what I ended up with, with some of comments for clarity:

function cassidyCluster(input) {
    // It's more "proper" to input an actual array here
    // but this is for accepting a string as well
    const list = typeof input === "string" ? input.split("") : [...input];
    const listLength = list.length;

    // Helper to reverse a portion of the list
    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;

        // Get the rightmost cluster of identical elements
        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 no more clusters need to be completed, break
        if (right <= 0) break;

        if (right < listLength - 1) {
            // When the rightmost cluster is "done", reverse the section
            // of the list that includes the next cluster to be completed
            reverse(list, clusterStartingIndex, listLength - 1);
        } else {
            // Base case: reverse the section of the list that matches
            // the rightmost cluster
            reverse(list, frontOfReversingSection + 1, listLength - 1);
        }
    }
    return list;
}

Humans are neat

I think this is a really interesting problem in that… it’s way easier to solve this as a physical human being with objects in front of you than it is for a computer to solve it.

Computers don’t easily understand how to grab a group and flip them as we do. Our eyeballs have the “O(1) read” of the state in front of us, and we can just flip the pieces in one “move”.

Anyway, I’m certain that someone out there will tell me that this is inefficient and pointless, because it kind of is… but I had a great time messing with this while playing with my kiddos. Go math!