4 ms·

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 bou

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

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