3
$\begingroup$

As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the numbers used in that average are also returned).

Right now, I'm testing all 10 number combinations, recording them and their average in a list and getting the maximum average from that list.

As you know, though, when the set becomes too big (usually around 30 numbers), the time period the program takes to execute gets much larger, often way too large to be usable.

What would be an algorithm that cuts down on execution time, while achieving the same (or approximate) result?

EDIT: numbers are floats between 0 and 1.

$\endgroup$
2
$\begingroup$

Looking for a maximum average $m$ below a threshold $m_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s_{max}$. If you have to select $k = 10$ numbers among $N$, you have:

$s_{max} = k \times m_{max}$

now the question looks like a Knapsack problem with a forced number of selected items $k$. You can use a DP solution closed to the one solving Knapsack. I also assume $s_{max} > 0$ and all available numbers are strictly positives. Note, that you may apply a simple offset on all numbers and $m_{max}$ if any is negative.

Let's build a $k\times s_{max}$ array $A$ with $A[i, j]$, the index of the last number selected to have $i$ selected values for a total of $j$. $A$ is initially filled with an "null" value.

Then the pseudo algorithm is:

for n from 1 to N:
    v = n-th available value
    for i from k-1 to 1:
        for j from smax-v to 1:
            if A[i, j] is not null and A[i+1, j+v] is null then:
                A[i+1, j+v] = n  
    if A[1, v] is null:
        A[1, v] = n

The best sum you can obtain is the last $A[k, j]$ which is not null. Using the index in $A$, you can backtrack the subset. Note that $i$ and $j$ loops go backward, to be sure the same value is not used twice.

Complexity is $O(Nks_{max})$ in time and $O(ks_{max})$ in space.

If $s_{max}$ is large and $N$ quite small, a (key, value) structure (in fact $k$ of these structures) instead of $A$ may be much more efficient as you won't have to loop on all empty values.

$\endgroup$
  • $\begingroup$ I'm sorry, I should have added that my numbers are floats between 0 and 1. Is there a way to adapt this answer? I edited my question. $\endgroup$ – cabralpinto Jun 6 at 13:07
  • $\begingroup$ You can apply a constant factor to all numbers and the required average. Just keep multiplying with 10 until you have only integers (average may be floating and you round it down). $\endgroup$ – Vince Jun 6 at 13:15
  • $\begingroup$ I think I have failed to understand how this solution works. I'm not getting how the A array works. Is there a place where I can find more about this solution? What solution to the Knapsack problem is this based on? $\endgroup$ – cabralpinto Jul 5 at 20:04
  • $\begingroup$ It is the dynamic programming solution for the 0/1 Knapsack problem. $\endgroup$ – Vince Jul 8 at 7:44
2
$\begingroup$

"Average < threshold" is equivalent to "Sum < 10 times threshold".

Find all subsets of five integers, and sort them in ascending order by their sum. That takes O (N over 5) space and O (N over 5, times log N) time.

Let S be the first, second, third subset and so on, as long as the sum of S is less than 5 x threshold. For each S find a subset T which is the last subset such that S + T have a sum less than 10 times the threshold. Finding all S and T is done in O (N over 5) time.

For each T, you need to find T' at the same or an earlier position such that S and T' have no element in common. Then S and T' are a candidate for the optimal sum. You can stop the search for T' once the sum of S and T' is not greater than the optimum value so far. It's hard to say how much finding T' contributes to the total execution time.

If you have many items, then the execution time may not a problem stopping you, but the O (N over 5) storage may very well be. But you don't have to store them all. To generate all subsets of 5 items in ascending order of sum: Store all sets of two items, and all sets of three items, sorted by their sums. Then you create a priority queue, with N over 2 items: Each item is one fixed subset of two items, combined with the smallest subset of three items, and without a common element. The priority queue gives you immediately the smallest subset of five items; then you replace that entry of (2 + 3) items with the same 2 items and the next largest 3 items. That gives you subsets with smallest sums in ascending order; another priority queue gives you the subsets in descending order of size.

The execution time is the same, but the storage requirement goes down to O (N over 3) instead of O (N over 5).

Find all sums of two elements in ascending order, call them $X_i$. Find all sums of three elements in ascending order, call them $Y_i$.

Take $X_1 + Y_1$, $X_2 + Y_1$, $X_3 + Y_1$ etc. and put them into a priority queue. Remove the smallest item which will be $X_i + Y_j$ for some i, j and insert $X_i + Y_{j_1}$ if $Y_{j+1}$ exists, and repeat. Obviously skip i, j where $X_i$ and $Y_j$. This gives you all sets of 5 items in ascending order of sum.

Have a second priority queue where you start with the highest $Y_j$ instead of $Y_1$, and extract the highest sum.

$\endgroup$
  • $\begingroup$ Nice idea to save space - not quite sure how it fits with For each S find a subset T …. $\endgroup$ – greybeard Jun 6 at 14:31
  • $\begingroup$ "That gives you subsets with smallest sums in ascending order". I cannot see how this can be correct. $\endgroup$ – Apass.Jack Jun 6 at 16:55
1
$\begingroup$

First, let us notice that if you replace 10 by 2 and the numbers are sorted, then you can solve this in linear time using a two pointer algorithm: one pointer starts at the bottom of the array, and the other one advances as far as possible while keeping the average below the threshold. Then you advance the first pointer by one and move the second one back until the average is below the threshold. And so on. We notice that the same algorithm also works for a weighted average.

Given $N$ numbers, you can divide them into two halves of $N/2$ numbers ("meet-in-the-middle"). Each set of 10 numbers splits into an $a$-set of the first half and a $b$-set of the second half, for some $a,b$ summing to 10. We can run the algorithm above for all such $a,b$ (using the appropriate weights). This will improve the running time from being proportional to $\binom{N}{10}$ to being proportional to $\binom{N/2}{10}$ (for $N \geq 20$).

You could try improving this further by partitioning into halves in a random fashion, and hoping for a balanced split, which will happen with reasonable probability. You then only have to try $a,b$ which are balanced. (The extreme would be to aim for $a=b=5$, but that's not necessarily the best choice.) While this is a randomized algorithm, it can probably be derandomized while taking only a small hit in the running time.

$\endgroup$
  • $\begingroup$ the other [pointer] advances as far as possible while keeping … starting where? advance the first pointer by one and move the second one back until the average is below the threshold does this require the set of [more that 30] numbers to be turned into an ascending array? I fail to understand the 2nd paragraph, starting with the switch from $N/2$ to 10. $\endgroup$ – greybeard May 30 at 21:09
  • $\begingroup$ Thanks, I forgot to mention that the list needs to be sorted. $\endgroup$ – Yuval Filmus May 31 at 4:30
1
$\begingroup$

Here is the outline of an algorithm that obtains the accurate result in $O({N\choose 5}N^2\log_2N)$ time. Its idea comes from meeting at the middle and two-pointer technique. In an ordinary setup, it yields the accurate result within a couple of seconds when given 50 numbers.

Assume the input numbers are given in an array. Selecting 10 numbers from the given multi-set of numbers is the same as selecting a subsequence of 10 elements. We first select the fifth element of the subsequence. Then we select 4 elements that sit before that fifth element. Then we select 5 elements that sit behind that fifth element. This selecting process ensures the same 10 numbers will not be selected twice.

$\newcommand{\sum}{\operatorname{sum}}$If $arr$ is an sequence of numbers, $\sum(arr)$ denotes the sum of all numbers in $arr$.

Algorithm

Input: A number $T$ and an array $arr$ of $N$ numbers

Output: 10 numbers in the array whose average is as large as possible but smaller than $T$, followed by the sum of them.

Procedure:

  1. Sort $arr$.
  2. For $i$ from 5 to $N-5$ exclusive:

    1. Collect all subsequences of the first $i$ elements of $arr$ where each subsequence has 5 elements, the last of which is $arr[i-1]$. Sort these subsequences by their sums. Let the sorted subsequences be $front5$.
    2. Collect all subsequences of the last $N-i$ elements of $arr$ where each subsequence has 5 elements, the first of which must be larger than $arr[i-1]$. Sort these subsequences by their sums. Let the sorted subsequences be $behind5$
    3. (two pointer technique.) Let $f$ be the first element in $front5$. Let $b$ be the largest element in $behind5$ such that $sum(f)+sum(b) <T$. Let subsequence $answer$ be the combination of $f$ and $b$.
      1. Let $f$ be the element in $front5$ after $f$. Search for the largest element $b$ in $behind5$ such that $sum(f)+sum(b) <T$. If $sum(f)+sum(b)>sum(answer)$, update $answer$ to be the combination of $f$ and $b$.
      2. Go back to the step above as long as $f$ is not the last element in $front5$.
  3. Output $answer$ and $sum(answer)$.

A few corner cases are not specified in the outline above. For example, if the average of any 10 numbers is no less than the threshold $T$, the algorithm can output something like "null".

An implementation in Java

Just click the "Run" button to see the result.

A subsequence can be viewed as a list of indices. For example, the subsequence $arr[0], arr[3], arr[5], arr[6], arr[12]$ can be treated as the list [0,3,5,6,12]. If $n\le64$, each index can be encoded in 6 bits. Then a subsequence of 5 elements can be encoded using a single 32-bit integer. A subsequence of 10 elements can be encoded using a single 64-bit integer.

$\endgroup$
  • $\begingroup$ I should have added that my numbers are not integers. Is there a way to adapt this answer? I'll edit my question. $\endgroup$ – cabralpinto Jun 6 at 13:02
  • $\begingroup$ Please check my new implementation that accepts floats. Note that the description of the algorithm does not restrict to integers. There is also a simple way to reuse my previous implementation. Just multiply each given float (which is between 0 and 1) by $2^{27}$. Rounding it to the nearest integer, we scale it to an integer between 0 and $2^{27}$. The result as an approximation might be good enough. $\endgroup$ – Apass.Jack Jun 6 at 16:58
  • $\begingroup$ Have been (and still are) busy with exams. Will take a careful look when everything settles! $\endgroup$ – cabralpinto Jun 12 at 13:34
  • $\begingroup$ Take your time. $\endgroup$ – Apass.Jack Jun 13 at 2:48
0
$\begingroup$

The biggest average of 10 is the average of the biggest 10.

A list of 10 isn't so time-consuming to maintain as a list of 30. Maintain a list of the 10 largest input integers that are less than the threshold. The list starts empty; unless and until it contains 10 integers, every input integer that is less than the threshold should be inserted into this list. Once the list contains 10, every time you read an integer $n$ which is less than the threshold, but bigger than the smallest $s$ in your list, replace $s$ by $n$ in the list.

$\endgroup$
  • 1
    $\begingroup$ The mean of the largest 10 elements lesser than some threshold $T$ is not neceassirly the largest mean (of any 10 elements) lesser than $T$. $\endgroup$ – lox May 29 at 19:36
  • $\begingroup$ Ah... it's the average that must $<T$, not the 10 numbers whose average was taken? The OP didn't make that clear. $\endgroup$ – Rosie F May 29 at 19:38
  • $\begingroup$ @RosieF yes, that's what I meant $\endgroup$ – cabralpinto May 29 at 20:12

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.