0

Can you think of a solution to the following seemingly simple algorithmic problem?

I am given a list of data points with scores and regions they belong to: [(9, A), (8, B), (7, A), (3, C), ...]. Scores are floats and each regions can have multiple data points assigned.

For each number N I'd like to select N data points from this list to maximize the total sum of these N scores. Without any restriction, you would chose the top scores, of course.

But now I have the constraint that in each region you have to pick at least X points or none at all. Therefore I cannot have a "sparse" region.

How would you solve this? An algorithm should output for each N the number of points chosen from each region.

4 Answers 4

1

I read your question a couple of times, I hope I got it right.

Having the scores of each region sorted in a list seems to be a handy thing to have.

  1. Compute if each region provides X data points. If it doesn't then it can only contribute 0 to the overall sum and therefore should be discarded.

  2. From all the regions, compute the maximum score they can contribute with only X data points. That means, find the X largest scores of A, B, etc.

  3. Now find the biggest of those X sums and add it to the overall sum You have to add N-X more elements to the overall sum, which can come from two sources, you should pick the bigger one that's possible with respect to the limitation that is imposed by N and add it to the overall sum:

    • The next biggest element of any of the already added areas. This element is not part of the X biggest elements already added to the overall sum. This will add 1 element.
    • The next biggest sum of X elements from another area. This is the sum of the biggest elements of that area. This will add X elements.

I keep mentioning the number of elements, because it might be tempting to add a whole new area, because that's likely to add a big number to the overall sum, but you have to be careful not to go beyond the N limit.

2
  • Seems valid, but how do you chose between 3a) and 3b)? 3b has X elements and is always larger than a single element from 3a. And is it possible to prove that the biggest sum (no.3) should always be included? Suppose I have X=2 and I want N=3 from 8A,7A,6B,6B,6B,1A. I should go for 3xB (=18), but the minimum regions for X=2 told me to favor A.
    – Gere
    Commented Jun 6, 2015 at 22:05
  • @Gerenuk well, if there was a proof, then you just disproved it =) You are right, my answer does not take this into account.
    – null
    Commented Jun 7, 2015 at 16:08
1

This is tricky. Obviously you ignore all regions with fewer than X scores. If N < X then there is no solution, except the trivial solution when N = 0. If X ≤ N < 2X then you must pick all N scores from the same region, which is either trivial to do optimally, or impossible. If X = 1, that's not a restriction, we just pick the highest scores.

What makes it tricky is that we don't even necessarily use the region where the top X scores added up are highest. Let's say X = 3 and N = 8, and scores (1001,1000,1000), (1000,1000,1000,1000), (1000,1000,1000,1000), (0,0,0,0,0). If we use 3 scores from the first region, we must use the scores from the last region, which is much worse than using the second and third region.

An optimal solution will pick k regions, where kx ≤ N and the total number of scores in these regions is ≥ N, pick the highest X scores from each region, then pick the remaining N - kx scores from those regions.

You might have to do an exhaustive search, excluding as many cases as possible. There are many things to reduce the number of cases in an exhaustive search.

We say that Region A > Region B if the sum of the highest X scores is same or higher, and if B has k scores for k > X then A also has k scores, and the sum of the highest k scores is the same or higher as well, and if all scores are the same then A must come first in your list of regions. With that definition, we don't need to look at solutions that contain B but not A. Depending on the data, that might exclude lots of possibilities.

If region R is less than several regions with a total of n scores then we can ignore region R completely. Region R may be "less than" two regions combined: If whatever scores we take from region R, we can equal or better with scores from A and B according to the rules, then we can ignore R if neither of A and B is part of the solution.

1
  • Sounds good. It's about as far as I got, too :) Comparing regions can be done with early cuts too. But it seem in the end one has to try out most subsets of regions. Once you decide on which regions to include, the task becomes easy, of course. Still, would be interesting to know if there is a magic trick to avoid exhaustively checking most sub-selections of regions.
    – Gere
    Commented Jun 9, 2015 at 19:55
0

I agree with @null's suggestion of having sorted lists for each region.

So how my approach to this problem would be :

  1. Create distinct sorted lists for each region such that they would be sorted based on their scores and you would have a different list for each region. Of course there are several ways of accomplishing this, which way you should use depends on your data set.
    For example at the end, you may have something like this:

    regionA = [(9,A),(6,A),(4,A)]
    regionB = [(7,B),(6,B),(5,B),(4,B)]
    regionC = [(15,C),(4,C)]
    
  2. After you've created your separate sorted lists for each region. Check if any list is shorter than X, if so discard this list.
    So for above example, say if X = 3, we would discard regionC.
  3. Now you should have separated sorted lists for regions that have more than X elements. Since they're already sorted by their scores, now all you have to do is; simply take the sums of scores of the highest/first(assuming descending sorting) N elements from each list and compare them. The highest sum you got is the selection you should go for.
    Example continued; let's take N = 3. We are left with regionA and regionB left now. For which the first 3 element sums would be sumA = 19, sumB = 18. In which case we would choose the region A.
1
  • How would you decide which region to include in step 3? You cannot take just the left-most highest score, since if you start a new region, you have to pick X at least.
    – Gere
    Commented Jun 9, 2015 at 19:48
0

I've used ideas from Gnasher's answer to write a Python script. It's undocumented and hard to read. But since this problem seems fairly standard and yet hard to solve, I'm posting this script for the desperate that might encounter this problem. The script misses an optimization for the exhaustive search. Instead it assumes a plain linear ordering A<B<C<... of regions in the variable possible_group_subsets.

from pprint import pprint
import random
from collections import Counter
import itertools as itoo
from operator import itemgetter
import cytoolz as tz


def merge_groupby(*datas, key=None):
    """
    datas should be sorted iterables

    returns [(key, [dat1, dat2, ...])] where key is ascending and dat* are data elements with that key
    key(dat) should be strictly increasing (not repeats) within each stream
    data will be iterated in data_iters as iterators
    it only needs to store len(datas) values

    Example:
    merge_groupby([1,2,3],[2]) -> [(1,[1]), (2,[2,2]), (3, [3])]
    """
    STOP_OBJ = object()
    if key is None:
        key = lambda x: x

    data_iters = [iter(d) for d in datas]
    head_values = []
    for d in data_iters:
        head_val = next(d, STOP_OBJ)
        head_key = key(head_val) if head_val is not STOP_OBJ else STOP_OBJ
        head_values.append((head_key, head_val))

    while not all(h[0] is STOP_OBJ for h in head_values):
        # print(head_values)
        min_key = min(filter(lambda x: x is not STOP_OBJ, tz.pluck(0, head_values)))
        result = []
        result_i = []
        for i in range(len(head_values)):
            head_key, head_val = head_values[i]
            if head_key == min_key:
                result.append(head_val)
                result_i.append(i)
        yield (min_key, result, result_i)

        # this needs to be at the end, so that the result is return before the next
        # element is read
        # otherwise groupby values groups might be automatically consumed/deleted if
        # the group advances
        for i in range(len(head_values)):
            head_key, head_val = head_values[i]
            if head_key == min_key:
                new_head_val = next(data_iters[i], STOP_OBJ)
                assert new_head_val is STOP_OBJ or new_head_val > head_val
                new_head_key = key(new_head_val) if new_head_val is not STOP_OBJ else STOP_OBJ
                head_values[i] = (new_head_key, new_head_val)


def pick(data, minsize):
    sum_groups_minsize = Counter()
    count_groups = Counter()
    for score, group, info in data:  # make one pass with sum and count
        if count_groups[group] < minsize:
            sum_groups_minsize[group] += score
        count_groups[group] += 1

    for group in list(sum_groups_minsize.keys()):  # remove small groups
        if count_groups[group] < minsize:
            del sum_groups_minsize[group]

    def group_select(groups):
        sum_score = sum(sum_groups_minsize[g] for g in groups)
        chosen_cnt = len(groups) * minsize
        seen_counter = Counter()
        for score, group, _info in data:
            if group not in groups:
                continue
            seen_counter[group] += 1
            if seen_counter[group] > minsize:
                sum_score += score
                chosen_cnt += 1
            yield chosen_cnt, sum_score, {g: max(seen_counter[g], minsize) for g in groups}

    # determine allowed group subsets
    sum_minsize_top = [group for group, summer in sorted(sum_groups_minsize.items(), key=lambda x: x[1], reverse=True)]
    possible_group_subsets = [sum_minsize_top[:num_groups_used] for
                              num_groups_used in range(1, len(sum_minsize_top) + 1)]

    # run algorithm
    group_iters0 = [group_select(group_subset) for group_subset in possible_group_subsets]
    group_iters1 = [itoo.groupby(g, key=itemgetter(0, 1)) for g in group_iters0]
    for chosen_cnt, head_group_iters, _head_group_idx in merge_groupby(*group_iters1, key=lambda x: x[0][0]):
        (best_group, best_score), best_grouper = max(head_group_iters, key=lambda x: x[0][1])
        _, sum_score, group_counts = list(best_grouper)[0]  # for tie scores just pick the first option
        yield (chosen_cnt, sum_score, group_counts)

res = list(pick(dat, minsize))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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