News for hackers. Stuff that matters.
Re:Show HN: How to store a set of four 5-bit values in one 1... by sabujp on Saturday January 27, 2018 @09:50PM (#16249488)
how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
Re:Show HN: How to store a set of four 5-bit values in one 1... by yorwba on Saturday January 27, 2018 @10:39PM (#16249648)
It'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_mul...

Re:Show HN: How to store a set of four 5-bit values in one 1... by jandrese on Saturday January 27, 2018 @10:50PM (#16249702)
He 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.
Re:Show HN: How to store a set of four 5-bit values in one 1... by lostatseajoshua on Sunday January 28, 2018 @12:58AM (#16250049)
I really don’t understand why not caring about the order would save space. Could you explain in simple terms please?
Re:Show HN: How to store a set of four 5-bit values in one 1... by jandrese on Sunday January 28, 2018 @05:03PM (#16253857)
If 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.

Re:Show HN: How to store a set of four 5-bit values in one 1... by pavlov on Sunday January 28, 2018 @01:46AM (#16250161)
Consider 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.

Re:Show HN: How to store a set of four 5-bit values in one 1... by hikkigaya on Saturday January 27, 2018 @10:15PM (#16249558)
I don't understand as well...
Re:Show HN: How to store a set of four 5-bit values in one 1... by 2opt on Sunday January 28, 2018 @12:21AM (#16249968)
(n + k - 1) choose k

n = number of unique 4-bit values

k = size of multiset

(2^4 + 4 - 1) choose 4 = 3876