c***7
发帖数: 315 | 1 Given a list, L, of size k. L contains elements between 1 and n. Also given
a function RND() such that this function returns a number between 1 and INT_
MAX.
Now generate number between 1 and n, using RND(), such that the element
should not be there in the list L. All elements should have a uniform
probability. |
b******t
发帖数: 965 | 2 rejection
RND()%n+1
如果出现在list里继续试
given
INT_
【在 c***7 的大作中提到】
: Given a list, L, of size k. L contains elements between 1 and n. Also given
: a function RND() such that this function returns a number between 1 and INT_
: MAX.
: Now generate number between 1 and n, using RND(), such that the element
: should not be there in the list L. All elements should have a uniform
: probability.
|
p*****2
发帖数: 21240 | 3
这个不能保证。uniform
probability
【在 b******t 的大作中提到】
: rejection
: RND()%n+1
: 如果出现在list里继续试
:
: given
: INT_
|
b******t
发帖数: 965 | 4 en 对 那个mod运算之前再做rejection就行了 如果 INT_MAX不是n的倍数
那就剩下的尾巴reject掉
【在 p*****2 的大作中提到】
:
: 这个不能保证。uniform
: probability
|
p*****2
发帖数: 21240 | 5
K很大的话，是不是效率不高？
【在 b******t 的大作中提到】
: en 对 那个mod运算之前再做rejection就行了 如果 INT_MAX不是n的倍数
: 那就剩下的尾巴reject掉
|
b******t
发帖数: 965 | 6 对 那样就把n-k个数列出来 然后map过去
【在 p*****2 的大作中提到】
:
: K很大的话，是不是效率不高？
|
g**********y
发帖数: 14569 | 7 这个应该是解。
x = RND()%(n-k), 然后数[1,n]第x个没有出现在L里的数。
【在 b******t 的大作中提到】
: 对 那样就把n-k个数列出来 然后map过去
|
c*****e
发帖数: 737 | 8 that's easy, 就是INT_MAX个map到n-k个。
先预处理一下，找出所有不在list里的数，放入一个array.
然后选array[rand() % array.size() - 1]。 |
p*****2
发帖数: 21240 | 9
有 bias
【在 g**********y 的大作中提到】
: 这个应该是解。
: x = RND()%(n-k), 然后数[1,n]第x个没有出现在L里的数。
|
c***7
发帖数: 315 | 10 Given a list, L, of size k. L contains elements between 1 and n. Also given
a function RND() such that this function returns a number between 1 and INT_
MAX.
Now generate number between 1 and n, using RND(), such that the element
should not be there in the list L. All elements should have a uniform
probability. |
|
|
b******t
发帖数: 965 | 11 rejection
RND()%n+1
如果出现在list里继续试
given
INT_
【在 c***7 的大作中提到】
: Given a list, L, of size k. L contains elements between 1 and n. Also given
: a function RND() such that this function returns a number between 1 and INT_
: MAX.
: Now generate number between 1 and n, using RND(), such that the element
: should not be there in the list L. All elements should have a uniform
: probability.
|
p*****2
发帖数: 21240 | 12
这个不能保证。uniform
probability
【在 b******t 的大作中提到】
: rejection
: RND()%n+1
: 如果出现在list里继续试
:
: given
: INT_
|
b******t
发帖数: 965 | 13 en 对 那个mod运算之前再做rejection就行了 如果 INT_MAX不是n的倍数
那就剩下的尾巴reject掉
【在 p*****2 的大作中提到】
:
: 这个不能保证。uniform
: probability
|
p*****2
发帖数: 21240 | 14
K很大的话，是不是效率不高？
【在 b******t 的大作中提到】
: en 对 那个mod运算之前再做rejection就行了 如果 INT_MAX不是n的倍数
: 那就剩下的尾巴reject掉
|
b******t
发帖数: 965 | 15 对 那样就把n-k个数列出来 然后map过去
【在 p*****2 的大作中提到】
:
: K很大的话，是不是效率不高？
|
g**********y
发帖数: 14569 | 16 这个应该是解。
x = RND()%(n-k), 然后数[1,n]第x个没有出现在L里的数。
【在 b******t 的大作中提到】
: 对 那样就把n-k个数列出来 然后map过去
|
c*****e
发帖数: 737 | 17 that's easy, 就是INT_MAX个map到n-k个。
先预处理一下，找出所有不在list里的数，放入一个array.
然后选array[rand() % array.size() - 1]。 |
p*****2
发帖数: 21240 | 18
有 bias
【在 g**********y 的大作中提到】
: 这个应该是解。
: x = RND()%(n-k), 然后数[1,n]第x个没有出现在L里的数。
|
P**l
发帖数: 3722 | 19 +1是啥意思
【在 b******t 的大作中提到】
: rejection
: RND()%n+1
: 如果出现在list里继续试
:
: given
: INT_
|
P**l
发帖数: 3722 | 20 k比n大咋办
【在 g**********y 的大作中提到】
: 这个应该是解。
: x = RND()%(n-k), 然后数[1,n]第x个没有出现在L里的数。
|
|
|
P**l
发帖数: 3722 | 21 直接给公式的各位为啥都觉得list里面没重复的元素呢？ |
p*****2
发帖数: 21240 | 22
有重复的也无所谓吧。预处理一下
【在 P**l 的大作中提到】
: 直接给公式的各位为啥都觉得list里面没重复的元素呢？
|
P**l
发帖数: 3722 | 23 错答案看久了就不会觉得错了。。
【在 p*****2 的大作中提到】
:
: 有重复的也无所谓吧。预处理一下
|
w****o
发帖数: 2260 | 24 什么是uniform probability?
比如抛硬币，正反面的概率相同，可是当你作实验的话，你抛10次，有可能这10次都是
正面，难道你能说不是uniform distribution?除非做大量实验，大数定律才能保证有
一半的正面和一半的反面。
【在 c***7 的大作中提到】
: Given a list, L, of size k. L contains elements between 1 and n. Also given
: a function RND() such that this function returns a number between 1 and INT_
: MAX.
: Now generate number between 1 and n, using RND(), such that the element
: should not be there in the list L. All elements should have a uniform
: probability.
|
w****o
发帖数: 2260 | 25 list L 里面有没有重复的数？
【在 c***7 的大作中提到】
: Given a list, L, of size k. L contains elements between 1 and n. Also given
: a function RND() such that this function returns a number between 1 and INT_
: MAX.
: Now generate number between 1 and n, using RND(), such that the element
: should not be there in the list L. All elements should have a uniform
: probability.
|
s******o
发帖数: 2233 | 26 why need -1 here?
shouldn't it just be array[rand() % array.size()]?
【在 c*****e 的大作中提到】
: that's easy, 就是INT_MAX个map到n-k个。
: 先预处理一下，找出所有不在list里的数，放入一个array.
: 然后选array[rand() % array.size() - 1]。
|
c*****e
发帖数: 737 | 27 数组从0开始的
【在 s******o 的大作中提到】
: why need -1 here?
: shouldn't it just be array[rand() % array.size()]?
|
s******o
发帖数: 2233 | 28 rand() % (array.size()) = [0, array.size()-1]
isn't it?
【在 c*****e 的大作中提到】
: 数组从0开始的
|
