What Every Programmer Should Know About Enumerative Combinatorics
leetarxiv.substack.com
leetarxiv.substack.com
From a purely mathematical point of view, why this choice of topics? You correctly point out that counting partitions has no closed formula, but there are a lot of related problems (Sitrling numbers of the two kinds for example) which are of more practical utility (e.g. they are related to sums of powers formulas). If that's too advanced for your audience then why not present more standard tricks like combinations with replacement aka stars and bars?
From a programmer's point of view, you could have focused more on how to generate subsets, permutations, partitions etc. in a memory-efficient way, for example how the Python stdlib does it.
Also, the factorial number system and the binomial base of univariate polynomials are definitely not "alternatives to base 2 in computer architectures".
Don't take this the wrong way but I struggle to see who you are writing for.
It can be interesting to know something (or even a lot) about enumerative combinatorics, and certainly there are some specific programming contexts in which that's a hard prerequisite, but it's not a topic that necessarily concerns every programmer.
OTOH I think it would greatly help programmers, especially beginners, to have fewer click baity titles around.
IMHO math in general is overrated for general purpose programming. I had plenty of math in college in the early nineties. I rarely need or use any of it. And when I do, I need to look up a lot of stuff for the simple reason that it's been decades since I last needed that knowledge. Very basic stuff even. Like highschool trigonometry (did some stuff with that a while back). Most programmers are just glorified plumbers that stick things together that others have built. They aren't designing new databases (for example) but simply using them. Which tends to be a lot easier. Though it helps to understand their general design and limitations. And if you are going to build a database, you might want to read up on a thing or two.
There is a wide range of esoteric topics you can dive into and learn a lot about. Diving into some of those in university is useful because it prepares you for a lifetime of needing to learn to wrap your head around random weird shit constantly that you need to understand to do the job. The point is not learning all that stuff upfront but simply learning enough that you can learn more when you need to. So, studying math and some other topics is a good preparation for that. You'll forget most of it if you don't use it. But when you need to, refreshing what you knew isn't that big of a deal.
The skill isn't in knowing that stuff but in being able to master that stuff.
I used a bunch of trigonometry when I was making 2D action games, getting characters to move about the screen and move smoothly at all sorts of angles, for one example. I also used Sine functions a lot for UI animations, making things looks like they're hovering or oscillating up and down.
I think one of the benefits of these classes, though, and university classes in general, is that even if you don't use or really remember the specifics decades later, you're at least aware of how these problems can be solved, and can look up and verify potential solutions much quicker than if you hadn't ever been exposed to it at all.
For a simple example, suppose you need to operate on `n` permutations of an enormous collection of data (far more than fits in RAM or disk), and you need those permutations to be re-usable.
One simple solution is to shuffle the indices `n` times and store the results in your cluster, but even the shuffle process is slow with normal techniques because of inter-machine random-access bandwidth issues. When using those shuffled indices for anything, you're again bandwidth-limited if the task doesn't require access of every index.
With just a tiny bit of a math background, you'll recognize that an O(1)-state shuffle is possible, where you can create some `Permutation` object with a `permute()` method, taking in an index and outputting the corresponding index in your hypothetical shuffle. That permutation will be CPU-bound rather than bandwidth-bound.
The problem with "being able to master stuff" is that your search process in the design space is slow. If I went and told you that an O(1)-state shuffle existed and would be good for the problem, sure, you'd be able to go code that up without issues. What's the chance that you'd even know to try though?
> wide range of esoteric topics ... prepares you for a lifetime of learning
That's part of it, but each of those esoteric topics also give new ideas something to latch onto. Our brains are associative, and being able to look at a new thing and tie it to a few esoteric concepts is a bit of a superpower, even if the association is weak. The difference between knowing nothing other than how to learn and knowing what's vaguely potentially possible or not is weeks or months of research. It's the difference between having to do the dumb, slow thing and being the person promoted for saving $1m/yr fixing whatever you wrote. You can get by for a long time, maybe your entire career, just making shit work, but if you're looking for more money or prestige then there are better routes.
> [...] esoteric topics also give new ideas something to latch onto. Our brains are associative, and being able to look at a new thing and tie it to a few esoteric concepts is a bit of a superpower, even if the association is weak. The difference between knowing nothing other than how to learn and knowing what's vaguely potentially possible or not is weeks or months of research.
The only point I'd add to your paragraph is that this applies to every domain when you're on the job, not just math. I live in constant terror of discovering that other disciplines solved my problem like a hundred years ago.
If the requirements are softer than "n random permutations", there might be a lot of potential solutions. It is very easy to come up with "n permutations" if you have no requirements on the randomness of them. Pick the lowest `k` such that `n < k!`, permute the first k elements leaving the rest in place, and now you have n distinct permutations storeable in `O(log(n)` (still not O(1) but close).
I know this is not really your point, but misusing `O(1)` is a huge pet peeve of mine.
Those sorts of applications would tend to not work well with a solution leaving most elements in the same place or with the same relative ordering.
The value isn't in knowing how to do math, it's in knowing when.
The value of a math class is far less in learning and remembering exactly how and, far more in learning what you can do with it so you can spot possible solutions when they arise. Expanding your mental toolkit.
Enumerative Combinatorics Considered Harmful
https://en.wikipedia.org/wiki/Twelvefold_way
This also takes care of most of discrete probability.
This sounds like to decode a single item you have to do work proportional to the cardinality of the set? Optimal space efficiency comes at a high computational overhead?
If you need to know how long that's going to take, you'll need to know some enumerative combinatorics.
What do you mean by "combinatorial data structures"?
The Hockey stick identity was something long forgotten and fun re-discovering.
The way they are generated not so much.
So, Sedgewick has an algorithm for generating permutations that are highly efficient, and ijust as difficult to grasp. But there is a paper out there where he explains the algorithm graphically, which makes it understandable.
So I haven't worked through the way to get the composition that is the n'th permutation yet, but I guess I will suffer.
It is not well written, and for instance the wrong term for partition, versus composition is made in the explanatory graphic at the top of the article.
Still, I think it was worth reading, I have made several programs utilizing permutations, and I might improve one or two of them after having read this, with some new knowledge.
But that's two compositions.
I think this article could really use more applied, concrete examples if it's intended for programmers.
It seems their idea for connecting math and programming was printing out a bunch of C code, without further motivation. But coding is an applied field, developpers will want a concrete idea of what they can do with it.
This is still too abstract.
> I think this article could really use more applied, concrete examples if it's intended for programmers.
> This is still too abstract.
I agree.
I think the article needs to demonstrate to the reader how every section is relevant to them - either by building off a relevant issue discussed in a previous section or tying it to some real world use case.
A Cyndi Lauper soundalike explains how many unique bands she can form by choosing from an expanding pool of musicians. Catchy!
> This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below.
These people are experts on sets but then they use the word "every" instead of "some" or "a subset of".
They just assume that everybody must be doing what they do. This is why Alan Kay said: “Point of View is worth 80 IQ points"