如何从随机位流中生成[0，n]范围内的随机整数而不浪费位？ [英] How to generate a random integer in the range [0,n] from a stream of random bits without wasting bits?

问题描述

我有一个（均匀）随机位流，我希望在[0，n]范围内统一生成随机整数，而不会浪费比特。 （我正在考虑超出楼层（log_2（n））+ 1的比特浪费，假设它总是可以使用不超过它。）例如，如果n = 5，那么算法我是寻找应该使用不超过三位。怎么办呢？

I have a stream of (uniform) random bits from which I'd like to generate random integers uniformly in the range [0,n] without wasting bits. (I'm considering bits wasted which are in excess of floor(log_2(n))+1, on the assumption that it's always possible to use no more than that.) E.g., if n = 5, then the algorithm I'm looking for should use no more than three bits. How can this be done?

推荐答案

这相当于找到两组不同（有限）基数之间的双向函数。这是不可能的。

This is equivalent to find a two-way function between two set of different (finite) cardinality. It is impossible.

这篇关于如何从随机位流中生成[0，n]范围内的随机整数而不浪费位？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！