Get random number without replacement in Solidity

Question

I am trying to sample a random number without replacement until the pool of possible numbers runs out, using Solidity. In pseudo-code, it should be something like this:

1. Initial pool of numbers: (1, 2, 3, 4)
2. Attempt 1: one of (1, 2, 3, 4) are possible, 3 is sampled
3. Attempt 2: one of (1, 2, 4) are possible, 4 is sampled
4. Attempt 3: one of (1, 2) are possible, 1 is sampled
5. Attempt 4: one of (2,) are possible, 2 is sampled
6. End

Note that each Attempt is a different call to the contract (by a different user/sender/wallet).

So far, the below code gets me a single random number within a range from 1 to 50:

uint256 public randomResult;

function fulfillRandomness(bytes32 requestId, uint256 randomness) internal override {
    randomResult = (randomness % 50) + 1;
}

I am stuck as to how do I get the pseudo-code's logic into a smart contract using Solidity. Preferably would like to avoid solutions that require iterations to check if number has been seen or not. Any help is appreciated. Thanks.

Answer 1

Assuming that your initial "deck of cards" is [0, 1, ..., N-1], the following should roughly work. I've made basically no attempt to compile or check this, but the underlying algorithm should be sound.

Roughly, the approach is this:

• You start with a sorted "deck of cards", [0, ..., N-1]. This deck is implicit.
• To pick a random card, you:
  • Choose a random location in the current deck
  • Pick the card at that location
  • Move the bottom card in the deck to your random location

This way, you can turn a uniform random integer generator into a stream of random integers without replacement, and each call is O(1) in time and space so you'll have no fundamental problems with the block gas limit.

Implementation-ish:

uint256 cardsRemaining;
mapping(uint256 => uint256) movedCards;

constructor(...) {
    [...]
    cardsRemaining = N;
}

// Return a random integer from 0 to k-1, inclusive.
// You might want to use, e.g, ChainLink, for random int generation.
function getRandom(uint256 k) private returns uint256 {
    [...]
}

function cardAt(uint256 i) private returns uint256 {
    if (movedCards[i]) {
        return movedCards[i];
    } else {
        return i;
    }
}

// Draw another "card" without replacement
function draw() public returns uint256 {
    require(cardsRemaining > 0, "All cards drawn");
    
    // Pick i
    uint256 i = getRandom(cardsRemaining);

    // Pick the ith card in the "deck"
    uint256 outCard = cardAt(i);

    // Move the last card in the deck into position i
    movedCards[i] = cardAt(cardsRemaining - 1);
    movedCards[cardsRemaining - 1] = 0;
    cardsRemaining -= 1;

    return outCard;
}