randomly find a combination from an array with duplicate elements and it's sum equal n

Question

How can I randomly find a combination from an array with duplicate elements and it's sum equal n.

Example

• array is [1, 2, 2, 3] and n is 3
• answers are 1+2, 1+2, 3
• If randomSubsetSum(array, n) is solution, then randomSubsetSum([1,2,2,3], 3) will return one of 1+2, 1+2, 3. Note: 1+2 appear twice as often as 3
• A real-world scenario: random selection of questions from a question bank for an exam

I found some similar questions and solutions:

1. Q: Finding all possible combinations of numbers to reach a given sum

   A: solution A and solution B

2. Q: Rank and unrank integer partition with k parts

   A: solution C

Defect

solution A and solution B can not random find combination. solution C does not allow duplicate elements.

My Java solution

public List<Integer> randomSubsetSum(List<Integer> list, Integer n) {
    list.removeIf(e -> e > n);
    int maxSum = list.stream().reduce(0, Integer::sum);
    if (maxSum < n) {
        throw new RuntimeException("maxSum of list lower than n!");
    }
    if (maxSum == n) {
        return list;
    }
    final SecureRandom random = new SecureRandom();
    // maybe helpful, not important
    final Map<Integer, List<Integer>> map = list.stream().collect(Collectors.groupingBy(Function.identity()));
    final List<Integer> keys = new ArrayList<>(map.keySet());
    final List<Integer> answers = new ArrayList<>();
    int sum = 0;
    while (true) {
        int keyIndex = random.nextInt(keys.size());
        Integer key = keys.get(keyIndex);
        sum += key;

        // sum equal n
        if (sum == n) {
            List<Integer> elements = map.get(key);
            answers.add(elements.get(random.nextInt(elements.size())));
            break;
        }

        // sum below n
        if (sum < n) {
            List<Integer> elements = map.get(key);
            answers.add(elements.remove(random.nextInt(elements.size())));
            if (elements.isEmpty()) {
                map.remove(key);
                keys.remove(keyIndex);
            }
            continue;
        }

        // sum over n: exists (below  = n - sum + key) in keys
        int below = n - sum + key;
        if (CollectionUtils.isNotEmpty(map.get(below))) {
            List<Integer> elements = map.get(below);
            answers.add(elements.get(random.nextInt(elements.size())));
            break;
        }

        // sum over n: exists (over  = sum - n) in answers
        int over = sum - n;
        int answerIndex =
                IntStream.range(0, answers.size())
                        .filter(index -> answers.get(index) == over)
                        .findFirst().orElse(-1);
        if (answerIndex != -1) {
            List<Integer> elements = map.get(key);
            answers.set(answerIndex, elements.get(random.nextInt(elements.size())));
            break;
        }

        // Point A. BUG: may occur infinite loop

        // sum over n: rollback sum
        sum -= key;
        // sum over n: remove min element in answer
        Integer minIndex =
                IntStream.range(0, answers.size())
                        .boxed()
                        .min(Comparator.comparing(answers::get))
                        // never occurred
                        .orElseThrow(RuntimeException::new);
        Integer element = answers.remove((int) minIndex);
        sum -= element;
        if (keys.contains(element)) {
            map.get(element).add(element);
        } else {
            keys.add(element);
            map.put(element, new ArrayList<>(Collections.singleton(element)));
        }
    }
    return answers;
}

At Point A, infinite loop may occur(eg. randomSubsetSum([3,4,8],13)) or use a lot of time. How to fix this bug or is there any other solution?

Heptameter

Why is not [1 1 1] allowed in your first example? What is the maximum size of the array? – Downey

Are all elements of a non-negative? – Prolegomenon

@CarySwoveland I hope this is a solution that supports negative numbers. – Heptameter

@Downey If array is [1,1,1] and n` is 3, then the array itself is the only answer. Array length may be in the hundreds or even over 1000. – Heptameter

I was suggesting 1+1+1 as an answer, not as an input. Sorry if it was not clear. – Downey

@Downey All elements in the answer must be selected from the given array. – Heptameter

And I suppose each element can only be selected once – Manicdepressive

Answer 1

Here is a solution lightly adapted from solution A.

from random import random

def random_subset_sum(array, target):
    sign = 1
    array = sorted(array)
    if target < 0:
        array = reversed(array)
        sign = -1
    # Checkpoint A

    last_index = {0: [[-1,1]]}
    for i in range(len(array)):
        for s in list(last_index.keys()):
            new_s = s + array[i]
            total = 0
            for index, count in last_index[s]:
                total += count
            if 0 < (new_s - target) * sign:
                pass # Cannot lead to target
            elif new_s in last_index:
                last_index[new_s].append([i,total])
            else:
                last_index[new_s] = [[i, total]]
    # Checkpoint B

    answer_indexes = []
    last_choice = len(array)
    while -1 < last_choice:
        choice = None
        total = 0
        for i, count in last_index[target]:
            if last_choice <= i:
                break
            total += count
            if random() <= count / total:
                choice = i
        target -= array[choice]
        last_choice = choice
        if -1 < choice:
            answer_indexes.append(choice)

    return [array[i] for i in reversed(answer_indexes)]

Mesics