0
$\begingroup$

Recently I came across a problem I don't get may hands on:

Given p binary positions.

Let s be the number of "set-bits" (1 < s < p * 2^(p-1) - 1).

I need the maximal set of assigments that alltogether set s bits.

Example: p = 3, s = 8. ==> A "maximal" set: {(0,0,1), (0,1,0), (1,1,0), (0,1,1), (1,0,1)}

At the whole 8 bits are set.

"Maximal": There is no other set with 8 bits set, that has more than 5 elements.

What I need is an algorithmic way to construct a maximal set.

Apart from that: get the number of elements of the maximal set without constructing it.

Any ideas appreciated!

NB: The problem is from partitioning a set most evenly.

The limits for s:

0 and p * 2^(p-1) are trivial, greater is handled by inverted symmetric.

$\endgroup$
2
  • $\begingroup$ Where did you encounter this? Can you credit or link to the original source? $\endgroup$
    – D.W.
    Commented Apr 5, 2023 at 19:14
  • $\begingroup$ The "original source" is just method I'm programming to build most even partitions. $\endgroup$
    – User42
    Commented Apr 5, 2023 at 19:24

1 Answer 1

0
$\begingroup$

You can greedily add elements from least bits set to most until you have more than $s$ total bits and then remove one of the elements (based on their number of set bits) to fix it.

To only count the number of elements you can sum $ \binom{p}1 + 2\binom p 2 + 3\binom p 3 + ...$ until it is greater than $s$, then figure out (using division) how many elements of the greatest bit count you need to remove to get a number less than $s$. If you find that to be $x$ $k$-weight elements the answer would be $\binom p 0 + \binom p 1 + ... + \binom p k - x$.

$\endgroup$
2
  • $\begingroup$ You can see that at any point during the algorithm the set has the least amount of set bits possible for a set of that size, since if any set has less set bits than one of its elements must have more set bits than any of the algorithm's set elements, which could be changed to an element with even less set bits, which shows no such set can be optimal, and thus no such set exists. $\endgroup$ Commented Apr 5, 2023 at 20:11
  • $\begingroup$ Thank you! Seeing it before me, I wonder why I had such a problem with it. Still the alg and count description seems to be incorrect in detail, concerning the elements to remove if sum > s, as the to removed elements don't have to be the largest ones already in the list (?). $\endgroup$
    – User42
    Commented Apr 6, 2023 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.