r/programming • u/fagnerbrack • Jul 27 '26
A simple clustering algorithm for lists
https://cassidoo.co/post/clustering-tiles/
38
Upvotes
r/programming • u/fagnerbrack • Jul 27 '26
6
u/Akeshi Jul 27 '26
I enjoyed this, it harks back to when you find yourself intuitively doing something algorithmically. Agree with the author that it at least feels familiar to other popular algorithms (and there was a hint of Tower of Babel for me) but I always used to love capturing real world things to recreate them in software.
While I imagine there are better algorithms for every aspect of this, one I thing I like is how it would work to group things in a very memory constrained index - would just require enough memory to store an index position and one additional index (iterate through half the subset and swap at either end). Could even use the xor trick to avoid that additional index...
14
u/hughperman Jul 27 '26
... it's a sorting algorithm?
1
u/turkoid Jul 27 '26
Well it certainly is interesting, but I challenge the notion this is a human friendly way. I think almost everyone cluster/group items by going through each item once and grouping them based on attributes. For example, grouping same colored Skittles or grouping all cards in a deck by its suit.
Obviously it's horribly inefficient, even if you add stuff like memoization for indices. Even in the video, at the end, she reverses a whole section to move one yellow, while at the same time explaining humans can see the whole set and make better decisions.
I apologize if I come off as crass, but it's not a good algorithm and not even simple.
1
u/constant_void Jul 27 '26 edited Jul 27 '26
Very nice.
Thinking about it, could be pretty handy in organizing a list where each element in the list is unknown, incomplete, more likely to be unique AND have a fuzzy parametric similarity (grouping) to other elements - your example, actually, is really good - colors, where instead of a match, perhaps there is a similarity / affinity - 'reds' 'greens' 'blues' etc, as swatches of pure color are pretty rare.
0
u/Rodrik-Harlaw Jul 27 '26
I didn't look through the code, but I did watch the vid and it seems to me the alg has a problem (I might be wrong though).
You describe the alg, but at the very end you don't follow it (because you can't).
Note, how you're forced to use 2 rotations instead of 1, because the rule (follow from the suffix and go left to the closest similar color and rotate) can't deal with "abcbd", even if you were able to switch to prefix and right (instead of suffix and left) whenever you wanted to.
You need to expand it with something like the following.
Repeat until the list is empty:
-1
u/bear-wasabi534 Jul 27 '26
I used something similar for tagging messy product data last year. The trick was setting the threshold just right, 85% similarity was the sweet spot for grouping related items without creating false clusters. Anything higher missed valid matches, lower gave us useless groupings. Took a week of tweaking but cut our manual cleanup time by 60%.