# Get random number without replacement in Solidity

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.

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;
}
``````
• 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. 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! Oct 18, 2021 at 15:28