5 ms·

A maximally-dense encoding for n-choose-k (2013)

58 points by bmc7505 4y ago

bmc7505 4y ago
I am curious if there is a similar bijection for mapping all subsets whose size is at most k with the natural numbers? The problem of minimally representing bounded-cardinality subsets is mentioned briefly under “Open Questions”, but I was unable to find a suitable solution. My first guess would be to encode each fixed-length subset family positionally, but this encoding still has some redundancy.
- mota7 4y ago
  Yes. The formulation in the blog post is a bit messy, but possibly more general way to think about it is something like: 0. set y = 1. set x = 0. 1. How many possible choices are there _given what we've picked so far_? Call it N. 2. Pick one of them. Call it 'a'. 3. set x = x + a * y. set y = y * N. 4. Repeat steps 1-3 until the number of choices drops to be less than 2. Decoding is the same thing in reverse. Start with x. mod it with the first N. that's the first choice. divide by N, mod with the number of remaining choices. that's the second choice. etc. For the case of n choose k, we get the rule that we can't pick anything lower than what has been picked so far. This means that first choice is one of (n-k+1) items. (We can't pick higher than that as we'd run out of choices before we reached k). With this construction, we can see your case is easy. You just need to be able to signal that some choice was the last choice. So the each choice is from a set of N+1, being the N possibilities plus "picked nothing". Picking nothing means there's no remaining choices so it terminates.
  - xeyownt 4y ago
    Great! Very clear. This should be the TL;DR... or the dense formulation of the dense encoding ;-)
  - lifthrasiir 4y ago
    This is an easy formulation but not necessarily optimal. In particular the step 1 is not well defined, and any further definition results in a non-optimal encoding. Say we have n = 6 and k = 3 and we've already seen 4; what are possible choices at this point? If you allow 3 here it would be equivalent to picking 3 first then 4 and there would be a redundant encoding. You can "fix" this by fixing the order, so without a loss of generality let's assume a strictly increasing order. Then the worst case would be (1, 2, 3), where N is respectively 6, 5 and 4, resulting in log_2 120 = 6.90 bits of information entropy instead of the optimal log_2 24 = 4.32 bits. The real fix would involve counting each subcases. There are 10 strictly increasing sequences starting with 1, 6 starting with 2, 3 starting with 3 and one starting with 4. The step 1 should account for this non-uniform distribution at the first place. The combinatorial number system described in the OP does this automatically.
    - mota7 4y ago
      For the first case, you can't pick a number lower than any existing number. So if 4 is already picked, then only 5 or 6 can be picked, but if we pick 6, then there's no third number available to pick, so there only 1 possibility (picking 5). So it terminates. The worst case of (1,2,3) is respectively 4, 3 and 2, resulting in log_2 24 = 4.32 bits. The first choice isn't picking from 6, it's picking from 4. (because if 5 or 6 are chosen, then there's not enough following numbers to be able to choose 2 more numbers). That's the piece about '(n-k+1) choices for the first number'. 5 or 6 are not possible choices given the ordering requirement.
      - lifthrasiir 4y ago
        > The worst case of (1,2,3) is respectively 4, 3 and 2, resulting in log_2 24 = 4.32 bits. The first choice isn't picking from 6, it's picking from 4. Oh, you are correct that the first number has only 4 possible choices. But what about the second number? It can't be 1 (already picked) and 6 (ordering requirement), but other numbers are open to pick. The third number is no different, it can't be 1 and 2 (already picked) but otherwise all other numbers are allowed. The resulting N would be 4, 4 and 4, i.e. 6 bits. Maybe it helps to see the fuller picture: 1st 2nd 3rd 2^(expected # of bits) 1 2 3, 4, 5, 6 64 1 3 4, 5, 6 48 1 4 5, 6 32 1 5 6 16 2 3 4, 5, 6 36 2 4 5, 6 24 2 5 6 12 3 4 5, 6 16 3 5 6 8 4 5 6 4 Ideally (and necessarily) the last column should be 24 for all possible cases, but your algorithm can go anywhere from 4 (2 bits) to 64 (6 bits).
        mota7 4y ago
        Nuts, you are correct that it isn't optimal. It's not quite as simple as just 2 bits per digit, because the last digit can only be large if the earlier digits are small. This makes the worst case is (1,2,6) which encodes as 48, for 5.58 bits.
- deleted 4y ago
  [deleted]
- Someone 4y ago
  There is. If you have a bijection between the items of some finite set S and {1,…,n} and a bijection between the items of some other finite set T disjunct with S and {1,…,m}, constructing a bijection between S ∪ T and {1,…,n+m} is trivial. For example, map the items of S to {1,n} as before and the items of T to {n+1,…n+m}, adding n to each of the values that you originally mapped each item of T to. If you have a third finite set disjunct with S and T, it’s disjunct with S ∪ T, so you can repeat this construction. “All subsets whose size is at most k” is the union of “all subsets whose size is zero”, “all subsets whose size is 1”, “all subsets whose size is 2”, … “ all subsets whose size is k”, and those sets are finite and disjunct, so you can use the above to construct such a mapping. (as long as the set of common items is computable, “disjunct” is not essential in the above, but it would make the mapping more complex. “Finite” also isn’t necessary, as long as they’re countably infinite and you have finitely many sets. I think even a countably infinite number of countably infinite sets would work)
  - dahart 4y ago
    Isn’t that mapping ambiguous? Maybe I’m mission something, but if you have a number to decode, say n+4, how you do differentiate between (3,n+1) and (2,n+2) and (1,n+3)?
    - Someone 4y ago
      If you have to decode n+4, you know the result can’t be in S, as its elements are mapped to {1,…,n}. So, the result is in T. You subtract n, leaving 4, and use whatever bijection you had for T to decode that into an element of T. If, on the other hand, you had n-4, you know it must decode to an element of S, and directly use its decoder to find that element.
  - bmc7505 4y ago
    How do you map a Natural to the corresponding subset in O(1), while still preserving the compactness of the fixed-size combination encoding? That’s the key property we want from our bounded-length encoding.
    - 4y ago
stncls 4y ago
As betrayed by the reference to Google+, this needs a (2013).
EricBurnett 4y ago
If efficiently calculating this mapping is of interest, see also http://www.thelowlyprogrammer.com/2010/04/indexing-and-enumerating-subsets-of.html http://www.thelowlyprogrammer.com/2010/04/indexing-and-enume... . (Python isn't my usual language these days, but this is a great example where the seamless bigint support shines. The number of possible sets grows fast!)
raymondh 4y ago
For those who want to explore these ideas in Python, see the nth_combination() and random_combination() recipes in the itertools docs¹ or just install them from more-itertools². # Find the 48,001st combination from 32 choose 8 >>> nth_combination(range(32), 8, 48000) (0, 1, 2, 5, 11, 21, 27, 28) ¹ https://docs.python.org/3/library/itertools.html#module-itertools https://docs.python.org/3/library/itertools.html#module-iter... ² https://more-itertools.readthedocs.io/en/stable/ https://more-itertools.readthedocs.io/en/stable/
wishawa 4y ago
For the open question on bounded number of choices, the idea is still "count the number of smaller combinations". Given a k-combination C, we first count the number of all possible combinations of less than k elements; this is binom(n, 0) + binom(n, 1) + ... + binom(n, k-1). Then we simply add the number of smaller combinations that are of k elements; this is the N calculated by the formula in the blog. The final answer is N' = binom(n, 0) + binom(n, 1) + ... + binom(n, k-1) + binom(C_k, k) + binom(C_{k-1}, k-1) + ... + binom(C_1, 1).
goldenkey 4y ago
I made an interactive Svelte app that will show the decimal number that each permutation maps to, as well as its utf-8 and base64 encoding. 32 choose 8: https://svelte.dev/repl/08e1d6bbaf4f417ea43a168c2b5ecb91 https://svelte.dev/repl/08e1d6bbaf4f417ea43a168c2b5ecb91 3 Dice: https://svelte.dev/repl/6c9f4d8d5f3b4b3cac08b985f64540a3 https://svelte.dev/repl/6c9f4d8d5f3b4b3cac08b985f64540a3
bjourne 4y ago
Very cool. One use that comes to mind is encoding chords. They usually consist of about 4 (or fewer) notes chosen from 3 octaves (36 notes). It could have applications in machine learning.
tromp 4y ago
I recently wrote a Haskell module [1] for computing with so-called Rankings, which I formalize as a triple consisting of a size, an unrank function that maps integers in the range 0..size-1 to objects, and a rank function that maps objects to integers. A similar Haskell module [2] was written by Brent Yorgey. The multinomialRanking function in my module generalizes the binomial rankings considered in the article, as well as permutations. By composing all kinds of rankings together, some very interesting classes of objects can be enumerated. Even very densely coded chess positions; by nesting 14 different rankings, I obtained a ranking of size ~ 8.7x10^45 that includes all legal chess positions. Sampling millions of random chess positions [3] and determining their legality [4] allowed us to estimate the number of legal chess positions as ~ 4.8 * 10^44. [1] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://hackage.haskell.org/package/simple-enumeration-0.2/docs/Data-Enumeration-Invertible.html https://hackage.haskell.org/package/simple-enumeration-0.2/d... [3] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking [4] https://github.com/peterosterlund2/texel/blob/master/doc/proofgame.md https://github.com/peterosterlund2/texel/blob/master/doc/pro...
- thfuran 4y ago
  Are there any legal chess positions that cannot be arrived at by a legal move from a legal position?
  - anonymoushn 4y ago
    "legal chess position" is probably defined in terms of being able to arrive at it by legal moves from legal positions.
  - tromp 4y ago
    A legal position is any position reachable from the starting position by a valid game of chess, i.e. a sequence of legal moves. Thus there are no such positions. Every legal position can be arrived at by playing a legal move from another legal position. That includes the starting position, since Nf3 Nf6 Ng1 Ng8 cycles back to it.
fjfaase 4y ago
When I read the title, for a moment I thought that this was about finding a maximal subset of n-choose-k vectors for a given distance d, such that all combination of vectors differ at atleast d positions.
SiempreViernes 4y ago
> "Last month" oh, ok, something new > "[...] Google+ post" Wait a minute, this isn't recent at all!
deleted 4y ago
[deleted]
nullc 4y ago
At the heart of the opus audio codec is a maximally-encoding for combinations with replacement and sign[1], which is n-choose-k where n can be reused and there is a sign for each chosen dimension. Or stated another way, n dimensional integer vectors where the sum of absolute values add to k. This enumeration can be implemented with the same kind of recursion as in the link, with a little bit of elaboration. Though interestingly, it (and the formula in the link) can also be be implemented with recursive table lookups quite efficiently, and for small fixed N with closed form formula (also true for the simpler combination code in the link). These maximally dense algebraic codes can be designed for a great many possible applications. For example, for a generational rolling cuckoo filter Pieter Wuille and I came up with an algebraic code for coding 4 sorted generation numbers with the requirement that all 4 are within a window of half the total range[2]. In prior published work on cuckoo filters used a large table of all possible values of combinations with replacement (to efficiently pack small sorted numbers). We found the algebraic code to be faster than a big dumb table, presumably due to cache locality, even though our fastest encoder/decoder still use tables but only tiny ones (at least for the sizes we were considering). A challenge for implementing these sorts of functions is that their inverses often require operations like integer square or cube roots which are not particularly fast unless the ranges are small enough to implement them with tables. [1] https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 [2] https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/src/cuckoofilter.cpp#L39 https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...

58 points by bmc7505 4y ago

I am curious if there is a similar bijection for mapping all subsets whose size is at most k with the natural numbers? The problem of minimally representing bounded-cardinality subsets is mentioned briefly under “Open Questions”, but I was unable to find a suitable solution. My first guess would be to encode each fixed-length subset family positionally, but this encoding still has some redundancy.

mota7 4y ago
Yes. The formulation in the blog post is a bit messy, but possibly more general way to think about it is something like: 0. set y = 1. set x = 0. 1. How many possible choices are there _given what we've picked so far_? Call it N. 2. Pick one of them. Call it 'a'. 3. set x = x + a * y. set y = y * N. 4. Repeat steps 1-3 until the number of choices drops to be less than 2. Decoding is the same thing in reverse. Start with x. mod it with the first N. that's the first choice. divide by N, mod with the number of remaining choices. that's the second choice. etc. For the case of n choose k, we get the rule that we can't pick anything lower than what has been picked so far. This means that first choice is one of (n-k+1) items. (We can't pick higher than that as we'd run out of choices before we reached k). With this construction, we can see your case is easy. You just need to be able to signal that some choice was the last choice. So the each choice is from a set of N+1, being the N possibilities plus "picked nothing". Picking nothing means there's no remaining choices so it terminates.
- xeyownt 4y ago
  Great! Very clear. This should be the TL;DR... or the dense formulation of the dense encoding ;-)
- lifthrasiir 4y ago
  This is an easy formulation but not necessarily optimal. In particular the step 1 is not well defined, and any further definition results in a non-optimal encoding. Say we have n = 6 and k = 3 and we've already seen 4; what are possible choices at this point? If you allow 3 here it would be equivalent to picking 3 first then 4 and there would be a redundant encoding. You can "fix" this by fixing the order, so without a loss of generality let's assume a strictly increasing order. Then the worst case would be (1, 2, 3), where N is respectively 6, 5 and 4, resulting in log_2 120 = 6.90 bits of information entropy instead of the optimal log_2 24 = 4.32 bits. The real fix would involve counting each subcases. There are 10 strictly increasing sequences starting with 1, 6 starting with 2, 3 starting with 3 and one starting with 4. The step 1 should account for this non-uniform distribution at the first place. The combinatorial number system described in the OP does this automatically.
  - mota7 4y ago
    For the first case, you can't pick a number lower than any existing number. So if 4 is already picked, then only 5 or 6 can be picked, but if we pick 6, then there's no third number available to pick, so there only 1 possibility (picking 5). So it terminates. The worst case of (1,2,3) is respectively 4, 3 and 2, resulting in log_2 24 = 4.32 bits. The first choice isn't picking from 6, it's picking from 4. (because if 5 or 6 are chosen, then there's not enough following numbers to be able to choose 2 more numbers). That's the piece about '(n-k+1) choices for the first number'. 5 or 6 are not possible choices given the ordering requirement.
    - lifthrasiir 4y ago
      > The worst case of (1,2,3) is respectively 4, 3 and 2, resulting in log_2 24 = 4.32 bits. The first choice isn't picking from 6, it's picking from 4. Oh, you are correct that the first number has only 4 possible choices. But what about the second number? It can't be 1 (already picked) and 6 (ordering requirement), but other numbers are open to pick. The third number is no different, it can't be 1 and 2 (already picked) but otherwise all other numbers are allowed. The resulting N would be 4, 4 and 4, i.e. 6 bits. Maybe it helps to see the fuller picture: 1st 2nd 3rd 2^(expected # of bits) 1 2 3, 4, 5, 6 64 1 3 4, 5, 6 48 1 4 5, 6 32 1 5 6 16 2 3 4, 5, 6 36 2 4 5, 6 24 2 5 6 12 3 4 5, 6 16 3 5 6 8 4 5 6 4 Ideally (and necessarily) the last column should be 24 for all possible cases, but your algorithm can go anywhere from 4 (2 bits) to 64 (6 bits).
      - mota7 4y ago
        Nuts, you are correct that it isn't optimal. It's not quite as simple as just 2 bits per digit, because the last digit can only be large if the earlier digits are small. This makes the worst case is (1,2,6) which encodes as 48, for 5.58 bits.
deleted 4y ago
[deleted]
Someone 4y ago
There is. If you have a bijection between the items of some finite set S and {1,…,n} and a bijection between the items of some other finite set T disjunct with S and {1,…,m}, constructing a bijection between S ∪ T and {1,…,n+m} is trivial. For example, map the items of S to {1,n} as before and the items of T to {n+1,…n+m}, adding n to each of the values that you originally mapped each item of T to. If you have a third finite set disjunct with S and T, it’s disjunct with S ∪ T, so you can repeat this construction. “All subsets whose size is at most k” is the union of “all subsets whose size is zero”, “all subsets whose size is 1”, “all subsets whose size is 2”, … “ all subsets whose size is k”, and those sets are finite and disjunct, so you can use the above to construct such a mapping. (as long as the set of common items is computable, “disjunct” is not essential in the above, but it would make the mapping more complex. “Finite” also isn’t necessary, as long as they’re countably infinite and you have finitely many sets. I think even a countably infinite number of countably infinite sets would work)
- dahart 4y ago
  Isn’t that mapping ambiguous? Maybe I’m mission something, but if you have a number to decode, say n+4, how you do differentiate between (3,n+1) and (2,n+2) and (1,n+3)?
  - Someone 4y ago
    If you have to decode n+4, you know the result can’t be in S, as its elements are mapped to {1,…,n}. So, the result is in T. You subtract n, leaving 4, and use whatever bijection you had for T to decode that into an element of T. If, on the other hand, you had n-4, you know it must decode to an element of S, and directly use its decoder to find that element.
- bmc7505 4y ago
  How do you map a Natural to the corresponding subset in O(1), while still preserving the compactness of the fixed-size combination encoding? That’s the key property we want from our bounded-length encoding.
  - 4y ago

stncls 4y ago

As betrayed by the reference to Google+, this needs a (2013).

EricBurnett 4y ago

If efficiently calculating this mapping is of interest, see also http://www.thelowlyprogrammer.com/2010/04/indexing-and-enumerating-subsets-of.html http://www.thelowlyprogrammer.com/2010/04/indexing-and-enume... . (Python isn't my usual language these days, but this is a great example where the seamless bigint support shines. The number of possible sets grows fast!)

raymondh 4y ago

For those who want to explore these ideas in Python, see the nth_combination() and random_combination() recipes in the itertools docs¹ or just install them from more-itertools². # Find the 48,001st combination from 32 choose 8 >>> nth_combination(range(32), 8, 48000) (0, 1, 2, 5, 11, 21, 27, 28) ¹ https://docs.python.org/3/library/itertools.html#module-itertools https://docs.python.org/3/library/itertools.html#module-iter... ² https://more-itertools.readthedocs.io/en/stable/ https://more-itertools.readthedocs.io/en/stable/

wishawa 4y ago

For the open question on bounded number of choices, the idea is still "count the number of smaller combinations". Given a k-combination C, we first count the number of all possible combinations of less than k elements; this is binom(n, 0) + binom(n, 1) + ... + binom(n, k-1). Then we simply add the number of smaller combinations that are of k elements; this is the N calculated by the formula in the blog. The final answer is N' = binom(n, 0) + binom(n, 1) + ... + binom(n, k-1) + binom(C_k, k) + binom(C_{k-1}, k-1) + ... + binom(C_1, 1).

goldenkey 4y ago

I made an interactive Svelte app that will show the decimal number that each permutation maps to, as well as its utf-8 and base64 encoding. 32 choose 8: https://svelte.dev/repl/08e1d6bbaf4f417ea43a168c2b5ecb91 https://svelte.dev/repl/08e1d6bbaf4f417ea43a168c2b5ecb91 3 Dice: https://svelte.dev/repl/6c9f4d8d5f3b4b3cac08b985f64540a3 https://svelte.dev/repl/6c9f4d8d5f3b4b3cac08b985f64540a3

bjourne 4y ago

Very cool. One use that comes to mind is encoding chords. They usually consist of about 4 (or fewer) notes chosen from 3 octaves (36 notes). It could have applications in machine learning.

tromp 4y ago

I recently wrote a Haskell module [1] for computing with so-called Rankings, which I formalize as a triple consisting of a size, an unrank function that maps integers in the range 0..size-1 to objects, and a rank function that maps objects to integers. A similar Haskell module [2] was written by Brent Yorgey. The multinomialRanking function in my module generalizes the binomial rankings considered in the article, as well as permutations. By composing all kinds of rankings together, some very interesting classes of objects can be enumerated. Even very densely coded chess positions; by nesting 14 different rankings, I obtained a ranking of size ~ 8.7x10^45 that includes all legal chess positions. Sampling millions of random chess positions [3] and determining their legality [4] allowed us to estimate the number of legal chess positions as ~ 4.8 * 10^44. [1] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://hackage.haskell.org/package/simple-enumeration-0.2/docs/Data-Enumeration-Invertible.html https://hackage.haskell.org/package/simple-enumeration-0.2/d... [3] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking [4] https://github.com/peterosterlund2/texel/blob/master/doc/proofgame.md https://github.com/peterosterlund2/texel/blob/master/doc/pro...

thfuran 4y ago
Are there any legal chess positions that cannot be arrived at by a legal move from a legal position?
- anonymoushn 4y ago
  "legal chess position" is probably defined in terms of being able to arrive at it by legal moves from legal positions.
- tromp 4y ago
  A legal position is any position reachable from the starting position by a valid game of chess, i.e. a sequence of legal moves. Thus there are no such positions. Every legal position can be arrived at by playing a legal move from another legal position. That includes the starting position, since Nf3 Nf6 Ng1 Ng8 cycles back to it.

fjfaase 4y ago

When I read the title, for a moment I thought that this was about finding a maximal subset of n-choose-k vectors for a given distance d, such that all combination of vectors differ at atleast d positions.

SiempreViernes 4y ago

> "Last month" oh, ok, something new > "[...] Google+ post" Wait a minute, this isn't recent at all!

deleted 4y ago

[deleted]

nullc 4y ago

At the heart of the opus audio codec is a maximally-encoding for combinations with replacement and sign[1], which is n-choose-k where n can be reused and there is a sign for each chosen dimension. Or stated another way, n dimensional integer vectors where the sum of absolute values add to k. This enumeration can be implemented with the same kind of recursion as in the link, with a little bit of elaboration. Though interestingly, it (and the formula in the link) can also be be implemented with recursive table lookups quite efficiently, and for small fixed N with closed form formula (also true for the simpler combination code in the link). These maximally dense algebraic codes can be designed for a great many possible applications. For example, for a generational rolling cuckoo filter Pieter Wuille and I came up with an algebraic code for coding 4 sorted generation numbers with the requirement that all 4 are within a window of half the total range[2]. In prior published work on cuckoo filters used a large table of all possible values of combinations with replacement (to efficiently pack small sorted numbers). We found the algebraic code to be faster than a big dumb table, presumably due to cache locality, even though our fastest encoder/decoder still use tables but only tiny ones (at least for the sizes we were considering). A challenge for implementing these sorts of functions is that their inverses often require operations like integer square or cube roots which are not particularly fast unless the ranges are small enough to implement them with tables. [1] https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 [2] https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/src/cuckoofilter.cpp#L39 https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...