1

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.

1 Answer 1

2

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;
}
2
  • Hi, sorry for the late reply, it took me awhile to fully understand it, but after some back and forth with other methods, I think this is a good solution. The only thing I would do differently is replace movedCards[cardsRemaining - 1] = 0; with cardsRemaining -= 1; as by default, each item in movedCards are all 0 (non initialized). cardsRemaining would then help with generating the random number via chainlink VRF.
    – user82768
    Oct 18, 2021 at 14:36
  • Ah -- you definitely want cardsRemaining -= 1;, edited my answer to add it. I'd keep movedCards[cardsRemaining - 1] = 0; around though. Per the semantics of the function it's not needed, but in those cases where you actually have set that array member, it'll refund a little gas due to state-space cleanup. Also, it's good blockchain citizenship to zero out your EVM state space when you're done with it!
    – fiddlemath
    Oct 18, 2021 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.