我有一个范围
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}}
最佳答案
一般来说,如果 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) 可以获得更好的精度
如果在某个步骤中找不到任何数字,请原路返回
希望对你有帮助
关于algorithm - 从总和等于 S 的范围中选择 K 个唯一随机数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34764758/