在不使用列表的情况下生成范围内唯一随机数的算法

Question

我正在 PHP 中寻找一种有效的算法来生成指定范围内的唯一随机数（开始 = 0 到结束 = 0xFFFFFFFF），而不使用列表来存储所有可能的数字。我已经探索了各种方法，但每种方法似乎都需要维护所有可能数字的列表，由于内存限制，这对于大范围是不可行的。当所有可能的数字都已返回后，就可以再次使用整个数字范围。

有没有一种方法可以在不将所有可能的数字存储在内存中的情况下完成此任务？我考虑过使用哈希函数或排列算法，但我不确定最佳方法或是否有更有效的解决方案。任何见解或代码示例将不胜感激。谢谢！

Answer 1

一个简单/天真的解决方案可以通过普通人的审查，但在任何有决心的人的审查下立即崩溃，那就是简单地根据定义的密钥对位进行加扰。

class ShuffleKey {
    
    private $key;
    
    public static function newKey(int $size=32) {
        $key = range(1,$size);
        shuffle($key);
        return new self($key);
    }
    
    public function __construct(array $key) {
        $this->key = $key;
    }
    
    public function getKey(bool $invert=false) {
        if( $invert ) {
            return array_flip($this->key);
        } else {
            return $this->key;
        }
    }
}

class IntegerShuffler {
    public function __construct(protected Shufflekey $key) {}
    
    public function shuffle($in) {
        return $this->_shuffle($in, $this->key->getKey());
    }
    
    public function unshuffle($in) {
        return $this->_shuffle($in, $this->key->getKey(true));
    }
    
    protected function _shuffle($in, $key) {
        $out = 0;
        foreach( $key as $offset => $transform ) {
            $out = $this->setBitAt($out, $transform, $this->getBitAt($in, $offset));
        }
        return $out;
    }
    
    protected function getBitAt(int $value, int $position) {
        return ( $value >> $position ) & 1;
    }
    
    protected function setBitAt(int $value, int $position, int $bit) {
        return $value | ( $bit << $position );
    }
}

// json_encode(ShuffleKey::newKey()->getKey())
$key = json_decode('[20,22,31,27,6,32,8,21,11,4,25,9,3,13,23,30,12,18,17,2,7,1,16,28,10,26,14,24,19,29,15,5]', true);

$shuf = new IntegerShuffler(new ShuffleKey($key));

var_dump(
    $t = $shuf->shuffle(1234567890),
    $shuf->unshuffle($t)
);

输出：

int(291931600)
int(1234567890)

通过这种方式，您可以按顺序遍历范围，边走边打乱，并且能够“重新洗牌”任意数字。

如果您需要的东西实际上经得起哪怕是最少量的审查，那么您应该考虑诸如“线性同余发生器”或“线性反馈移位寄存器”之类的东西，如“President James K. Polk”在《President James K. Polk》中所建议的那样。评论。 【注：评论者，不是美国第11任总统。】 如果您需要“适当的”安全性，那么您必须深入了解 StackExchange 的 Math 和/或

InfoSec

部分，以获得适当强大的方法，正如 Barmar 在评论中所建议的那样。