Let say we have the following set $S = \{x_1, x_2, x_3, ..., x_n\}$ where $x_i$ is a real number between $0$ and $1$.

Now I want to find an algorithm that randomly generates a subset of $S$, free to for each $x$ choose an arbitrary real number between $0$ and $1$, with the following constraint:
$x_1 + x_2 + ... + x_n = B$, where $B$ being a budget of some sort.

Examples of a subset would be (given $B = 2$ and $n = 10$) are:
$\{x_1 = 0.6, x_2 = 0.4, x_{3} = 1\}$, $\{x_1 = 0.2, x_2 = 0.8, x_{3} = 0.5, x_{7} = 0.5\}$, etc.

Now lets look at a more complex version. Say I don't like that $\{1, 1\}$ has the same "cost" as $\{0.5, 0.5, 0.5, 0.5\}$. Instead I want the cost to be exponential, making it very expensive to choose values closer to $1$. In addition I want to add a constant cost to make it more cost-effective to focus on a few stronger values, preventing results like $\{0.00000001, 0.00000001, ..., 0.0000001\}$. The above constraint would then instead be:
$f(x) = C \ \operatorname{sgn}(x) + ke^{ax}$,
where $C, a, k$ are constants, and $$f(x_1) + f(x_2) + f(x_3) + ... + f(x_n) = B ,$$

where $f(x)$ is a cost function of sorts.

To clarify, I'm not necessarily looking for subsets that exactly add up to $B$, instead I'm looking for something that is somehow bounded by $B$, making different subsets generated by the same algorithm to be comparable to each other in a "fair" sort of way.

Now I posted this here at stackoverflow where I got the advice to try here instead. I realize now though that I probably didn't explain it very well over there.

  • 2
    $\begingroup$ I think the problem is still underspecified. How do you know that there is any subset of $S$ that sums to $B$? How do you know that there is more than one? Do you really require that the sum is no more than $B$? $\endgroup$ – Craig Sep 15 '11 at 23:25
  • $\begingroup$ Well I don't really want it to sum exactly B, but at least no more than B. What I want is to be able to generate subsets of S through some randomized process while upholding some sort of "fairness" between the results. $\endgroup$ – moevi Sep 15 '11 at 23:42

A not-so-mathematical but easy approach is to generate random subsets and then filter for those that satisfy the condition (i.e. generate new ones until one satisfies it). Condition e.g. Sum in some range.

Not mathematically proved (here) but "right by intuition" (IMHO): You could split the set in multiple parts, asigning randomly to each one a sub-budget such that they add up to B (if you use 2 halves this is trivial). Do this recursively on the parts using the sub-budgets. If you reach a set containing only one element, assign the sub-budget to it(for this run). (Guessed asymptotic time complexity: $\Theta(n)$ if $n$ is the number of set elements)

  • $\begingroup$ To get some random variation on B you could e.g. choose a randomized B on each run. $\endgroup$ – marzipankaiser Oct 4 '14 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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