Hacker News new | past | comments | ask | show | jobs | submit login

Combinations, not permutations. This seems to be a somewhat common misuse of terminology – maybe because "permutations" sounds cooler and more mathy?



Yeah, that's true. Someone at some point started using the term wrong and it stuck. Kind of like the words occlude and albedo which are also typically used incorrectly in graphics.


It is jargon, i think pretty much any field has those - though graphics and gamedev have a lot of their own (sometimes conflicting).

My favorite is "brush" to mean convex polyhedron. I remember when i joined a gamedev company years ago and was looking around the editor and noticed some buttons with a paintbrush - clicking it didn't do anything and after asking around it turned out this was for making in-editor 3d geometry but the artist who made the icon (we wanted to release the editor which meant someone went and remade all the programmer-made icons) didn't knew about it or about the terminology (i think the original programmer-made icon had the word "brush"), so he just drew what the button was supposedly about: a brush :-P.


I just went through this a couple of weeks ago. I joined a game dev company recently and I’ve been experiencing a lot of it. Another is calling everything a particle for physics simulations. Please let me know if you can think of any other.


How are they used and how should they be used?


A permutation is any of the possible ways to turn a set into an ordered list. For example, the set {1,2,3} has the following permutations:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

A set of n elements has n! (n factorial) permutations: you have n options to pick the first element, n-1 to pick the second element, and so on.

A combination of a set is one of its subsets, including the set itself and the empty set. The set {1,2,3} has the following subsets:

{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

A set of n elements has exactly 2^n combinations; for each element you either include or exclude it.


in permutations the ordering of the individual elements is important (a different order of exactly the same elements is a different permutation), but it's irrelevant in uber shaders. they should just say combinations (different elements are toggled on and off).


Yes. With combinations, you get a combinatorial explosion.

With permutations, you get—IIRC, the factorial?—which is much, much worse. Mistaking permutations for combinations isn’t a small error.


IIRC with combinations you get factorials (n!) while with permutations you get n^n.


With permutations without repetitions you get factorials (n!) while with permutations with repetitions you get n^n.

More precisely, when taking N objects out of M, the number of permutations is always computed by multiplying N factors, which are either all equal to M when repetitions are allowed (i.e. the power M^N) or they are decreasing by one at each factor when the extracted objects must be unique (i.e. M*(M-1)*(M-2) ...), which gives the factorial in the case of N taken out of N.

With combinations either with or without repetitions you also get a product of N factors, but each factor is much smaller, being a ratio of two integers, instead of the integer that is the numerator. This is usually written in a form that is useless for actual computation, as the ratio between a factorial and the product of other two factorials (which differ between the two kinds of combinations).

The sum of all combinations without repetitions is 2^N (when repetitions are allowed, the sum is infinite).


Welp, no wonder I had to redo my engineering mathematics course.

Thanks for the correction.


Nope. Combinations are subsets: you either include or exclude each element. So 2^n. With permutations, you have n options for the first element, (n-1) options for the second, and so on. Thus n! possibilities total.


Ah, sorry, I meant the correct an incorrect usages for "occlude" and "albedo".




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: