Skip to content

Instantly share code, notes, and snippets.

@cleanunicorn
Created October 6, 2021 09:55
Show Gist options
  • Save cleanunicorn/d27484a2488e0eecec8ce23a0ad4f20b to your computer and use it in GitHub Desktop.
Save cleanunicorn/d27484a2488e0eecec8ce23a0ad4f20b to your computer and use it in GitHub Desktop.
Fisher Yates Shuffle, aka Knuth Shuffle proof of concept
contract Shuffle {
function shuffle(
uint size,
uint entropy
)
public
pure
returns (
uint[] memory
) {
uint[] memory result = new uint[](size);
// Initialize array.
for (uint i = 0; i < size; i++) {
result[i] = i + 1;
}
// Set the initial randomness based on the provided entropy.
bytes32 random = keccak256(abi.encodePacked(entropy));
// Set the last item of the array which will be swapped.
uint last_item = size - 1;
// We need to do `size - 1` iterations to completely shuffle the array.
for (uint i = 1; i < size - 1; i++) {
// Select a number based on the randomness.
uint selected_item = uint(random) % last_item;
// Swap items `selected_item <> last_item`.
uint aux = result[last_item];
result[last_item] = result[selected_item];
result[selected_item] = aux;
// Decrease the size of the possible shuffle
// to preserve the already shuffled items.
// The already shuffled items are at the end of the array.
last_item--;
// Generate new randomness.
random = keccak256(abi.encodePacked(random));
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment