从包含重复元素的数组中随机找到一个组合，其和等于n

Question

如何从具有重复元素且其和等于n的数组中随机找到一个组合。

示例

• 数组是[1,2,2,3]和n是3
• 答案是12，12，3
• 如果randomSubsetSum（array，n）是解决方案，那么randomSubsetSum（[1,2,2,3]，3）将返回12，12，3中的一个。注意：12出现的频率是3
• 一个真实的场景：随机选择题库中的试题进行考试

我发现了一些类似的问题和解决方案：

>

A：方案A和方案B

Q：具有k个部分的秩和非秩整数分区

A:解决方案C

缺点

解决方案A和解决方案B无法随机找到组合<代码>解决方案C不允许重复元素。

我的Java解决方案

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;
}

在点A，可能会出现无限循环（例如随机子循环（[3,4,8]，13））或使用大量时间。如何修复这个错误，或者有其他解决方案吗？

Answer 1

如果我做对了，核心任务是过滤具有特定总和的子集，并返回一个随机的。由于任务不是想出如何构建给定列表的所有子集的算法，我建议使用一个库来为你完成这项任务。其中一个库是组合库。如果你碰巧已经使用了ApacheCommons或Guava，他们也实现了一些方法来获取列表的所有子集。

使用cominatoricSlib3获取子集非常简单：

Generator.subset(List.of(1, 2, 2, 3))
        .simple()
        .stream()
        .forEach(System.out::println);

得到：

[]
[1]
[2]
[1, 2]
[2]
[1, 2]
[2, 2]
[1, 2, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[2, 3]
[1, 2, 3]
[2, 2, 3]
[1, 2, 2, 3]

对于上面描述的任务，以下内容可以作为使用上述lib外包子集查找的起点：

import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import org.paukov.combinatorics3.Generator;

public class TestJavaClass {
    public static void main(String[] args) {
        System.out.println(randomSubsetSum(List.of(1, 2, 2, 3), 3));
    }

    public static List<Integer> randomSubsetSum(List<Integer> list, Integer n) {
        List<List<Integer>> subLists = Generator.subset(list)
                                                .simple()
                                                .stream()
                                                .filter(x -> !x.isEmpty())
                                                .filter(x -> sum(x).equals(n))
                                                .collect(Collectors.toList());
        if (!subLists.isEmpty()){
           return subLists.get(new Random().nextInt(subLists.size()));
        }
        else {
            throw new IllegalArgumentException("No subset found in: " + list + " having a sum = " + n);
        }
    }

    public static Integer sum(List<Integer> list) {
        return list.stream().reduce(0, Integer::sum);
    }
}

为了简单起见，我删除了边缘案例的处理。如果需要，请添加：

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;
}