随机选择两个值

在我的算法中，我有两个值，我需要随机选择，但每个值必须选择预定的次数。随机选择两个值

到目前为止，我的解决方案是将选择放入一个向量正确的次数，然后洗牌。在C++：

// Example choices (can be any positive int) 
int choice1 = 3; 
int choice2 = 4; 

int number_of_choice1s = 5; 
int number_of_choice2s = 1; 

std::vector<int> choices; 
for(int i = 0; i < number_of_choice1s; ++i) choices.push_back(choice1); 
for(int i = 0; i < number_of_choice2s; ++i) choices.push_back(choice2); 
std::random_shuffle(choices.begin(), choices.end());

然后我把一个迭代choices每当我需要一个新的我增加了迭代器，抓住价值。

这可行，但似乎可能有更有效的方法。因为我总是知道每个值的使用数量，所以我想知道是否有更多的算法来做这件事，而不是只存储这些值。

来源

2012-05-10 Sean Lynch

我会坚持工作的解决方案，除非有充分的理由不这样做。它被描述为瓶颈或类似的东西？ – amit

有一种方法，但它不那么清晰和简洁。我会坚持这种技术。 –

我其实很喜欢这个解决方案。想到的所有其他解决方案（思考约5秒后）都涉及随机数生成器。但是，由于每个选择都有一个预先确定的数量，所以这些解决方案将是无效的，因为他们最终必须在选择已经发生最大次数后开始忽略值。（不可否认，洗牌方法可能是CPU消耗，但至少可以使其成为可预测的运行时间，这与您在上面考虑的解决方案无关） – gnomed

你不必要地使用这么多的内存。你有两个变量：

int number_of_choice1s = 5; 
int number_of_choice2s = 1;

现在只需随机：

int result = rand() % (number_of_choice1s + number_of_choice2s); 
if(result < number_of_choice1s) { 
    --number_of_choice1s; 
    return choice1; 
} else { 
    --number_of_choice2s; 
    return choice2; 
}

这个尺度非常好两百万元的随机调用的。

来源

2012-05-10 20:02:26

一旦计数器达到0，您可以将该过程的其余部分短路 –

如何存在偏差？这看起来像Knuth从n算法中选择m的自定义版本 - 我的+1 – BrokenGlass

但请注意，如果您的标准库碰巧有一个糟糕的'rand'实现（例如，具有小模数的线性同余），则使用'％'像这样可以引入偏见。另外，'RAND_MAX'可能小到32767（微软标准库中的'rand'有这个属性），如果你有大量的选择可以完全丢失。 –

你可以多一点简单的写：

std::vector<int> choices(number_of_choice1s, choice1); 
choices.resize(number_of_choice1s + number_of_choice2s, choice2); 
std::random_shuffle(choices.begin(), choices.end());

来源

2012-05-10 20:40:33

一种有偏随机分布将保持某种顺序在结果集（即是选择了最有越来越少机会被挑选的选择下一步），这给了一个有偏见的结果（特别是如果你必须选择第一个值的次数比第二个值大，那么你最终会得到类似这样的结果{1,1,1,2,1,1 ，1,1,2}

下面是代码，看起来很像@Tomasz Nurkiewicz写的代码，但使用一个简单的偶/奇应该给出50/50的机会选择VA梅毒。

int result = rand(); 

if (result & 1 && number_of_choice1s > 0) 
{ 
number_of_choice1s--; 
return choice1; 
}else if (number_of_choice2s>0) 
{ 
number_of_choice2s--; 
return choice2; 
} 
else 
{ 
return -1; 
}

来源

2012-05-10 22:01:59

随机选择两个值

回答

相关问题