编程珠玑12章课后有个问题题目不理解。
原题是:
/**
* 第12章,第02题
* 12.1节要求所有的m元子集被选中的概率相等,这个条件比按等概率m/n选择每个整数更强 。
* 给出这样一个算法,其中每个元素的选中概率相等,但某些子集的选中概率比其他子集大一些。
**/
而题目的12.1节是这样要求的:
输入:m和n,使 0 < m < n ( m, n均为整数)
输出:m个随机整数的有序列表。(随机整数不允许重复)
不明白:这里问题具体所指的是什么意思?
1. m元子集是什么? (就是指那m个随机整数的有序列表吗?)
2. “m/n选择每个整数”指在整个n集合里面中的m集合中的每个整数被选中的概率?
3. 后面所讲的“某些子集的选中概率比其他子集”
“某些”是自己指定还是说随机的?
“其他子集”为什么会存在其他子集,它是将n元数组分割成了很多个子集的吗?
“其他子集”和“每个元素”选中的概率是相等的吗? 编程珠玑 编程 算法
[解决办法]
m元子集。好多年前的事了,现在还记得一点。
大意是这样:
比方说我们有一大串的随机数0和1,比方有10000个吧。
那么,在这10000个中,两个数成一对的00、01、10、11出现的概率应该是相当的,三个数成一对的000、001、010、011、100、101、110、111出现的概率也应该是相当的,四个数一对……以此类推。
两个数的称2元子集、三个数的称三元子集,等等
“某些子集的选 中概率比其他子集大些”,以2元子集为例,可能是01出现的概率明显比00、10、11出现的概率大。
大概就是这个意思吧,不知道有没有交代清楚。
[解决办法]
这个不存在强不强的问题。你只要理解成这个概率分布,和每个元素以m/n概率选中的概率分布不一样就可以了。