6 ms·

What Every Programmer Should Know About Enumerative Combinatorics

91 points by muragekibicho 1y ago

pestatije 1y ago
why?
- muragekibicho 1y ago
  Algorithms like HyperLoglog are an exercise in Enumerative Combinatorics
  - jpgvm 1y ago
    To add to this HyperLogLog, sketches and bloom filters are the magic that make most of modern distributed databases tick.
  - dgan 1y ago
    that's not a helpful response. Congrats on knowing that, but the rest of us are still in the dark about the usage
    - muragekibicho 1y ago
      the lion does not concern himself with real-world applications.
- discreteevent 1y ago
  >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 1y ago
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 1y ago
  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 1y ago
    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 1y ago
Don't the title illustration and the actual content of the article mix up which is which?
qsort 1y ago
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 1y ago
  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 1y ago
  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 https://www.efavdb.com/change
giomasce 1y ago
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 1y ago
  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 1y ago
  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.
  - 1y ago
relaxing 1y ago
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 https://youtu.be/w0i_ZFlGTVY?si=ThEcjtYvivMkBgcv
- zahlman 1y ago
  For me it's got to be "Nine Nine Nine".
rck 1y ago
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 https://en.wikipedia.org/wiki/Twelvefold_way This also takes care of most of discrete probability.
tmoertel 1y ago
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 1y ago
  https://github.blog/changelog/2021-10-31-warning-about-bidirectional-unicode-text/ https://github.blog/changelog/2021-10-31-warning-about-bidir... https://trojansource.codes/ https://trojansource.codes/
barbazoo 1y ago
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 1y ago
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 1y ago
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.
- mcphage 1y ago
  > combinatorial data structures What do you mean by "combinatorial data structures"?
qazxcvbnm 1y ago
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 1y ago
  That reminds me of https://everyuuid.com/ https://everyuuid.com/
- abeppu 1y ago
  > 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?
  - qazxcvbnm 1y ago
    Yeah, its a theoretical general connection. Once you’ve pinned down the specific structure and know how many structures to skip by virtue of knowing how to count them, it becomes a somewhat practical algorithm.
jmount 1y ago
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_algorithms) 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 1y ago
“Why every programmer should ignore articles with ‘every’ in the title”
rendaw 1y ago
I do think this is something that's relevant to most programmers unlike other commenters -- but the article goes from "counting database IDs" (a good practical use case!) to "integer partitions" and I was immediately lost. No explanation of how those relate to calculating the database ID space, how those fit into the bigger scheme, etc. 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.
McUsr 1y ago
I found the way of counting the number of permutations useful. 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.

91 points by muragekibicho 1y ago

pestatije 1y ago

why?

muragekibicho 1y ago
Algorithms like HyperLoglog are an exercise in Enumerative Combinatorics
- jpgvm 1y ago
  To add to this HyperLogLog, sketches and bloom filters are the magic that make most of modern distributed databases tick.
- dgan 1y ago
  that's not a helpful response. Congrats on knowing that, but the rest of us are still in the dark about the usage
  - muragekibicho 1y ago
    the lion does not concern himself with real-world applications.
discreteevent 1y ago
>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 1y ago

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 1y ago
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 1y ago
  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 1y ago

Don't the title illustration and the actual content of the article mix up which is which?

qsort 1y ago

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 1y ago
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 1y ago
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 https://www.efavdb.com/change

giomasce 1y ago

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 1y ago
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 1y ago
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.
- 1y ago

relaxing 1y ago

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 https://youtu.be/w0i_ZFlGTVY?si=ThEcjtYvivMkBgcv

zahlman 1y ago
For me it's got to be "Nine Nine Nine".

rck 1y ago

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 https://en.wikipedia.org/wiki/Twelvefold_way This also takes care of most of discrete probability.

tmoertel 1y ago

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 1y ago
https://github.blog/changelog/2021-10-31-warning-about-bidirectional-unicode-text/ https://github.blog/changelog/2021-10-31-warning-about-bidir... https://trojansource.codes/ https://trojansource.codes/

barbazoo 1y ago

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 1y ago

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 1y ago

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.

mcphage 1y ago
> combinatorial data structures What do you mean by "combinatorial data structures"?

qazxcvbnm 1y ago

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 1y ago
That reminds me of https://everyuuid.com/ https://everyuuid.com/
abeppu 1y ago
> 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?
- qazxcvbnm 1y ago
  Yeah, its a theoretical general connection. Once you’ve pinned down the specific structure and know how many structures to skip by virtue of knowing how to count them, it becomes a somewhat practical algorithm.

jmount 1y ago

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_algorithms) 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 1y ago

“Why every programmer should ignore articles with ‘every’ in the title”

rendaw 1y ago

I do think this is something that's relevant to most programmers unlike other commenters -- but the article goes from "counting database IDs" (a good practical use case!) to "integer partitions" and I was immediately lost. No explanation of how those relate to calculating the database ID space, how those fit into the bigger scheme, etc. 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.

McUsr 1y ago

I found the way of counting the number of permutations useful. 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.