 # Choosing subsets of a set such that the subsets satisfy a global constraint We have a set of items Lovellss 2022-06-24 Answered
Choosing subsets of a set such that the subsets satisfy a global constraint
We have a set of items $I=\left\{{i}_{1},{i}_{2},...,{i}_{n}\right\}$. Each of these items has what we call a $p$ value, which is some real number. We want to choose a subset of $I$, call it ${I}^{\prime }$, of size $m$ (for some m with $1\le m\le n$) such that the average of the $p$ values of the items in ${I}^{\prime }$ falls within some specified range, $\left[{p}_{l},{p}_{u}\right]$.
We hope to do this in $O\left(n\right)$ time, but any polynomial time algorithm is good enough. We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average $p$-value constraint.
Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.
Is there a way of doing this?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Odin Jacobson
Assuming $m$ is an input, your problem is NP-Complete.
Subset sum can be reduced to it.
Given $A=\left\{{x}_{1},...,{x}_{n}\right\}$ for which we need to find a subset of sum $S$, we can create $n$ inputs to your algorithm, with input $A$, $m$ and ${p}_{L}={p}_{U}=\frac{S}{m}$, for $1\le m\le n$.
If $m$ is fixed then the brute force algorithm is $O\left({n}^{m}\right)$ and so has a polynomial time algorithm.

We have step-by-step solutions for your answer!