# Assignment problem with maximal partitioning

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.

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

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$$.