<p>From my answer at math.stackexchange: <a href="https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207">https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207</a></p>

<p>Assuming $m$ is an input, your problem is NP-Complete.</p>

<p>Subset sum can be reduced to it.</p>

<p>Given $A = \\{x_{1}, ..., x_{n}\\}$ 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 \leq m \leq n$.</p>

<p>If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.</p>

<p>If this does not answer your question, can you please clarify exactly what you need?</p>

CC BY-SA 2.5
2010-08-24T17:28:31.557Z
2010-08-24T17:28:31.557Z
2017-04-13T12:19:19.363Z
Aryabhata
<p>We have a set of items $I = \{i_1, i_2, ..., i_n\}$.  Each of these items has what we call a <em>p</em> value, which is some real number.  We want to choose a subset of $I$, call it $I'$, of size $m$ (for some $m$ with $1 \le m \le n$) such that the average of the <em>p</em> values of the items in $I'$ falls within some specified range, $[p_l, p_u]$.  (For example, we might require an average <em>p</em> value between 0.70 and 0.74.)  Moreover, we want to do this efficiently.  </p>

<p>We hope to do this in O(n) 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.</p>

<p>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.</p>

<p>Is there a way of doing this?</p>

<co.combinatorics>
Choosing subsets of a set such that the subsets satisfy a global constraint
Paul Reiners
# Choosing subsets of a set such that the subsets satisfy a global constraint

(Asked by: username_0 on 2010-08-24)

We have a set of items $I = \{i\_1, i\_2, ..., i\_n\}$. 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'$, 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'$ falls within some specified range, $[p\_l, p\_u]$. (For example, we might require an average *p* value between 0.70 and 0.74.) Moreover, we want to do this efficiently.

We hope to do this in O(n) 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?

**Tags:** co.combinatorics

---

## 1 answers

### Answer by username_1 on 2010-08-24. Score: 5 | Accepted answer

From my answer at math.stackexchange: <https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207>

Assuming $m$ is an input, your problem is NP-Complete.

Subset sum can be reduced to it.

Given $A = \\{x\_{1}, ..., x\_{n}\\}$ 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 \leq m \leq n$.

If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.

If this does not answer your question, can you please clarify exactly what you need?


---

