[HN Gopher] What Every Programmer Should Know About Enumerative ...
___________________________________________________________________
What Every Programmer Should Know About Enumerative Combinatorics
Author : muragekibicho
Score : 77 points
Date : 2025-05-15 12:10 UTC (3 days ago)
(HTM) web link (leetarxiv.substack.com)
(TXT) w3m dump (leetarxiv.substack.com)
| pestatije wrote:
| why?
| muragekibicho wrote:
| Algorithms like HyperLoglog are an exercise in Enumerative
| Combinatorics
| jpgvm wrote:
| To add to this HyperLogLog, sketches and bloom filters are
| the magic that make most of modern distributed databases
| tick.
| dgan wrote:
| that's not a helpful response. Congrats on knowing that, but
| the rest of us are still in the dark about the usage
| discreteevent wrote:
| >Enumerative combinatorics is a branch of mathematics focused
| on counting the elements of a set.
|
| 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"
| johnisgood wrote:
| What is the difference between integer compositions and integer
| partitions? It says a composition is just an ordered partition of
| an integer, but according to this article, number 4 can be
| partitioned into 5 parts, but apparently has 8 compositions. I
| find the 8 compositions much more accurate, but I do not get why
| it would not have 8 partitions.
| tux3 wrote:
| 1 + 3 and 3 + 1 are the same partition of 4, because it's a sum
| with the same two numbers. The order of the 1 and the 3 doesn't
| matter for partitions.
|
| 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.
| johnisgood wrote:
| Thank you for the explanation, it definitely cleared things
| up for me.
|
| > I think this article could really use more applied,
| concrete examples if it's intended for programmers.
|
| > This is still too abstract.
|
| I agree.
| Etheryte wrote:
| Don't the title illustration and the actual content of the
| article mix up which is which?
| qsort wrote:
| I find the presentation a bit confusing and I'm already very
| familiar with this material.
|
| 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.
| FjordWarden wrote:
| I am just a simple web developer and I found this stuff
| interesting. Learning about array programming has taught me the
| importance of combinatorics and its possible application to GPU
| programming. It is just the first chapter in a series of
| articles, I'd say let the man cook.
| efavdb wrote:
| FWIW there is a way to count partitions with a fixed "basis".
| Eg I wrote a post here on how to count the number of ways to
| make change for a given amount of money:
|
| https://www.efavdb.com/change
| giomasce wrote:
| What Every Programmer Should Know About Enumerative Combinatorics
| -> Nothing.
|
| 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.
| globalnode wrote:
| Yep, also with little in the way of motivating examples and a
| pile of mathematics to sift through, its hard to devote the
| time to this.
| jillesvangurp wrote:
| This is easily verified by the notion that the overwhelmingly
| vast majority of programmers (myself included) probably know
| very little of the topic. Seemingly without that causing a lot
| of issues.
|
| 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.
| cableshaft wrote:
| Certain fields need it more than others. Graphics and vide
| game development needs more math than web app development
| (well, usually. Sometimes you need to implement a formula),
| including trigonometry.
|
| 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.
| donatj wrote:
| > 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
|
| 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.
| tikhonj wrote:
| There are lots of things that we _should_ collectively be
| doing as an industry but, largely, _aren 't_.
| hansvm wrote:
| There's value in "being able to master that stuff," and
| there's value in "having mastered that stuff." The latter
| lets you trim a lot of possible designs from your search
| space nearly instantly, letting you focus on routes which are
| actually viable. The former is only of similar power when you
| know the design in advance or there aren't many possible
| solutions.
|
| 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.
| thethirdone wrote:
| What "O(1)-state shuffle" could you possibly be talking
| about? It takes `O(nlogn)` space to store a permutation of
| list of length n. Any smaller and some permutations will be
| unrepresentable. I am very aware of this because shuffling
| a deck of cards correctly on a computer requires at least
| 200 random bits.
|
| 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.
| hansvm wrote:
| It's O(1) if you don't need access to every permutation
| (common in various monte carlo applications). 64-128 bits
| of entropy is good enough for a lot of applications, and
| that's all you get from any stdlib prng, so that's what I
| was comparing it to.
|
| 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.
| gopher_space wrote:
| > What's the chance that you'd even know to try though?
|
| > [...] 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.
| odyssey7 wrote:
| I don't know, I once messed up a Big Tech interview question
| that was about enumerative combinatorics.
| acheron wrote:
| Falsehoods Programmers Believe About Enumerative Combinatorics
|
| Enumerative Combinatorics Considered Harmful
| CamperBob2 wrote:
| Enumerative Combinatorics Is All You Need
| twoodfin wrote:
| Lambda: The Ultimate Enumerative Combinator
| relaxing wrote:
| Anyone else have the combinatorics song from Square One TV
| forever burned into their brain?
|
| A Cyndi Lauper soundalike explains how many unique bands she can
| form by choosing from an expanding pool of musicians. Catchy!
|
| https://youtu.be/w0i_ZFlGTVY?si=ThEcjtYvivMkBgcv
| zahlman wrote:
| For me it's got to be "Nine Nine Nine".
| rck wrote:
| Just about everything that a non-specialist in combinatorics
| needs to know about counting can be found in Rota's twelvefold
| way, which lists the 12 counting problems that you can define for
| finite sets and shows how to solve them:
|
| https://en.wikipedia.org/wiki/Twelvefold_way
|
| This also takes care of most of discrete probability.
| tmoertel wrote:
| What's the deal with this notice, presumably injected by GitHub
| into the hosted code samples in the article:
|
| > This file contains hidden or bidirectional Unicode text that
| may be interpreted or compiled differently than what appears
| below.
| david_allison wrote:
| https://github.blog/changelog/2021-10-31-warning-about-bidir...
|
| https://trojansource.codes/
| barbazoo wrote:
| I didn't quite get from the write up what it is that every
| programmer should know about enumerative combinatorics or why
| it's a relevant topic for programmers at all honestly.
| simpaticoder wrote:
| This has the flavor of a post written by a programmer who got a
| particularly interesting interview question. They continued
| working on it when they got home. Hey, it's happened to the best
| of us (I was once asked to write "tic tac toe" and at the time I
| was really getting into functional programming and simple data
| structures, and for some reason I didn't stop working on the
| problem for a few days because I wanted to generalize tic-tac-toe
| in scale, depth, e.g. deeply nested tic-tac-toe, and dimension,
| where the board has more than 2 dimensions) but I'm not sure I
| would have written a paper "What every programmer should know
| about implementing nested tic-tac-toe on large arrays in high
| dimensions" because the answer is, almost certainly, nothing.
| getnormality wrote:
| I think the best single thing for programmers to know about
| combinatorics is combinatorial data structures. If you have a
| collection of objects and you need to iterate over all possible
| combinations, subsets, or permutations of that collection,
| libraries like Python's itertools do this for you. The resulting
| code will be clearer, more concise, and more reliable than if you
| reinvent the wheel with some hand-coded rat's nest of loops.
|
| If you need to know how long that's going to take, you'll need to
| know some enumerative combinatorics.
| qazxcvbnm wrote:
| For those who are not aware, knowing how to count the number of
| structures is (nearly) the same as knowing how to encode said
| structure as an integer (space-optimally) (the naive general
| algorithm would not have good time complexity); to convert to
| integer, simply define some ordering on said structures,
| enumerate until you find your structure, the index of the
| structure is the integer encoding; conversely, to decode, simply
| list all structures and pick the structure with the index of the
| integer.
| manmal wrote:
| That reminds me of https://everyuuid.com/
| abeppu wrote:
| > simply list all structures and pick the structure with the
| index of the integer
|
| 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?
| jmount wrote:
| As a fan of combinatorics, I love people looking into the topic.
| Though most of what a programmer would find useful are
| approximations or trends which are handled well by the Master
| theorem (
| https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_al...
| ). For those deeply interested in the deep math of combinatorics
| I recommend Flajolet, Sedgewick, *Analytic Combinatorics,
| Cambridge 2009.
| louthy wrote:
| "Why every programmer should ignore articles with 'every' in the
| title"
___________________________________________________________________
(page generated 2025-05-18 23:01 UTC)