algorithm - 从总和等于 S 的范围中选择 K 个唯一随机数

Question

我有一个范围

R = {0, ..., N}

我喜欢获取总和等于 S 的 K 个元素，但这些元素应该是随机选择的。

因此，一种简单的蛮力方法是确定所有包含 K 数字的元素组合，从而产生 S 并随机选择其中一个组合。

我正在尝试考虑一个递归解决方案，其中选择一个随机数，然后问题减少到找到 (K-1) 个总和等于 (S - K0) 的随机数，但这不需要在解决方案中产生。

有没有更好的方法？

一个例子是:

R = {0,1,2,3,4,5}, S = 5, K = 2
Solutions: randomly pick one of {{1,4};{2,3};{0.5}}

Answer 1

一般来说，如果 K 很大(那么 N 也很大)，而 S 又不太小，这是不可预测的，因为，有两个很多的组合。

蛮力:尝试每一种组合。如果存在解决方案，您一定会找到解决方案，但如果有超过 1 Md 或更多的解决方案，则几乎不可能将它们全部列出。

您的算法:

要随机选择，您的算法没问题:随机取一个数字，然后取另一个，...

但是你做了一个假设:你选择的数字存在一个解决方案:你不知道。

那又怎样？如果统计上存在许多解决方案，您可以这样找到它，也许，或者也许不。

一些足迹:

1 使用 S/K

如果每个数字 < S/K，这是不可能的。

如果每个数字> S/K，那是不可能的。

所以让我们假设有数字 < S/K，和其他 > S/K

2 只保留数字 < S，如果 S 很小就很有趣。

3 想法:如果 S 很大，数字很小，则有可能存在很多组合。

算法思路

1随机取一个数N1

2 如果N1 < S/K，取另一个N2 > S/K

3 计算N1+N2:如果<2.S/K再取一个N3>S/K，如果不是

4 每一步迭代:如果sum < n S/K take another > S/K, if not

5 将 S/K 替换为 (S-sum N1,N2,...)/(K-n) 可以获得更好的精度

如果在某个步骤中找不到任何数字，请原路返回

希望对你有帮助