0

I have a big array of numbers and need to choose X of them randomly without repetition. I have a real random seed provided by an external oracle.

Is there a known fair algorithm to create a pseudo random generator based on the seed?

I read another answer that proposes the usage of modulo operator: Does something like this give an equal chance to each index?

(consider it untested pseudo-code)

uint256[10000] big_list_of_numbers;
seed = very_big_77_digits_number;
uint256[] results;

for(uint256 i =0; i< numbers_to_retrieve; i++) {
  uint256 random_index = seed % big_list_of_numbers.length;
  results.push(big_list_of_numbers[random_index])
  seed = seed - random_index
}

1 Answer 1

2

You can look at StackOS's lottery implementation - they have a function getRandomNumber that uses Link to generate a random seed randomNumber; it then uses hash on the seed+nonce to generate a random number.

They have an interesting way to avoid duplicates, the randomized number must be <= participants length, and each time a participant wins, it's moved to the end of the array so it won't be chosen again.

Applying this method on your code (untested) -

uint256[10000] big_list_of_numbers;
seed = very_big_77_digits_number;
uint256[] results;

for(uint256 i = 0; i < numbers_to_retrieve; i++) {
  uint256 random_index = uint256(keccak256(abi.encode(seed + i))) % (big_list_of_numbers.length - i);
  results.push(big_list_of_numbers[random_index]);

  big_list_of_numbers[random_index] =  big_list_of_numbers[big_list_of_numbers.length - i - 1];
  big_list_of_numbers[big_list_of_numbers.length - i - 1] = results[i];
}
1
  • thank you very much! this helped me a lot !
    – Stormsson
    May 17, 2022 at 16:58

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .