4 ms·
how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
by sabujp 9y ago
how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
- yorwba 9y agoIt's not the number of sets with at most 4 elements (which would be 1820), it's the number of bags with exactly 4 elements (i.e. the multiplicity of duplicate elements matters). https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_multisets https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul...
- jandrese 9y agoHe doesn't care about the order so 1, 2, 3, 4 is stored the same as 4, 3, 2, 1. That's where the savings is coming from.
- lostatseajoshua 9y agoI really don’t understand why not caring about the order would save space. Could you explain in simple terms please?
- pavlov 9y agoConsider the simplest case where your set members are just bits. If you have three bits and you care about the order, that's a 3-bit number -- it can take 8 different values. If you have those same bits but you don't care about the order, the operation is a "bit count" -- you can only have 4 different values.
- jandrese 9y agoIf you care about the order then 1, 2, 3, 4 has to be stored differently than 4, 3, 2, 1, as well as 1, 3, 2, 4, and so on. If you don't care about the order all of those can be stored in exactly the same way. Think of it like lossy compression, if you don't care about some of the detail you an ignore it (the order of the numbers in this case) and save some space.
- hikkigaya 9y agoI don't understand as well...
- 2opt 9y ago(n + k - 1) choose k n = number of unique 4-bit values k = size of multiset (2^4 + 4 - 1) choose 4 = 3876