Shuffle array/mapping

Question

Is it possible to shuffle the array or mapping of addresses? I tried this solution but it always returns the same result

 for (uint256 i = 0; i < arrayAddress.length; i++) {
            uint256 n = i + uint256(keccak256(abi.encodePacked(block.timestamp))) % (arrayAddress.length - i);
            address temp = arrayAddress[n];
            arrayAddress[n] = arrayAddress[i];
            arrayAddress[i] = temp;
        }

Answer 1

I created a simple solution for this. I used numbers instead of addresses to keep it simple and easy to visualize.

1. When using the block.timestamp and block.number, we need to be careful, since if the function (or the transaction) where you are using these values does not modify the state, then the block.timestamp and block.number will be the timestamp and block number of the last block that modified the state. Only when your function modifies the state that block.timestamp and block.number actually refer to different values. This may be the reason why you keep seeing the same results running your function multiple times, because block.timestamp is always the same (if you have not made any other transaction that modifies the state) and the keccak256 function is creating the same hashes, thus the same results.

2. Maybe calculating a keccak256 hash in every iteration of the for loop is not necessary. We could calculate a hash and then read each byte from it and use it as the value to create the index with the % operator that we need. Unless the length of our array is more than 256 elements, then we could read 2 bytes instead, which would provide us with about 65536 values, and so on. I suggest this because in case our array will never be more than 256 elements long, let's say that our array has 256 elements, we would only need to calculate the keccak256 hash only about 256 / 32 times, which is 8 times, instead of the worse case 256 times, which is more efficient.

3. Modifying the state in a loop may not be a good idea and we could get an out of gas exception. To help with this, we can copy the state data as memory, modify it, then save it to storage again after the loop ends.

4. If you function does not modify state, then you cannot rely on the block.timestamp or block.number. Then you would need to somehow provide the 'seed' for your keccak256 hash to be unique. Probably sending an extra parameter, a random number, etc., to your function so you use it instead of block.timestamp.

I wrote some code and put some comments and results below so you can see it, play with it and modify it:

// SPDX-License-Identifier: MIT
pragma solidity 0.8.16;

// Autor: Jeremy Then

contract Shuffle {

    uint[] public uints = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

    function getInts() public view returns(uint[] memory) {
        return uints;
    }

    // This shuffle function works by creating a keccak256 hash of the current block.timestamp + a counter
    // to produce a different hash every time we need one.
    // Then, we use each byte as our value to generate the index we are going to swap the ith element with
    // by using the modulo (%) operator.
    // A keccak256 hash only has 32 bytes, so, in case the array we are trying to shuffle is bigger than
    // 32 elements, then we create a different keccak256 hash with the counter, and start taking each
    // byte of this new hash one by one to derive the index to swap the ith element with..
    // This function asumes that the array to shuffle is no bigger than 255 elements. If so,
    // then we would need to read 2 bytes instead of one. Because 1 byte only provides us 256 (2^8) values
    // to use as index, but 2 bytes would provide us with 65536 (2^16) values to use as index, which 
    // we then cut it down to the range of our array using the % operator.
    function shuffle() public returns(uint[] memory) {

        // Making a copy of the uints array, since modifying it from storage is really expensive
        // and we could get a out of gas exception
        uint[] memory uintsCopy = uints;

        uint counter = 0;
        uint j = 0;
        bytes32 b32 = keccak256(abi.encodePacked(block.timestamp + counter));
        uint length = uintsCopy.length;

        for (uint256 i = 0; i < uintsCopy.length; i++) {

            if(j > 31) {
                b32 = keccak256(abi.encodePacked(block.timestamp + ++counter));
                j = 0;
            }

            uint8 value = uint8(b32[j++]);

            uint256 n = value % length;

            uint temp = uintsCopy[n];
            uintsCopy[n] = uintsCopy[i];
            uintsCopy[i] = temp;
        }

        // Now, modifying the state uints array, once as a whole.
        uints = uintsCopy;

        return uintsCopy;
        
    }

    // Since this function does not modify the state and does not pay gas,
    // the `block.timestamp` will be the timestamp of the last block that modified the state
    // of this contract.
    // If another function is called that cause a state change, then that is an actual
    // transaction that was mined, paid gas and then block.timestamp will be the timestamp of the
    // block of that last transaction.
    function getTimestamp() public view returns(uint) {
        return block.timestamp;
    }

    // Since this function does not modify the state and does not pay gas,
    // the `block.number` will be the block number of the last block that modified the state
    // of this contract
    function getBlocknumber() public view returns(uint) {
        return block.number;
    }
    
}

// Running the shuffle function multiple times, it produced shuffled values like these:

// 15,12,5,2,19,10,16,1,3,11,20,9,7,13,8,6,18,4,17,14
// 11,1,4,9,16,3,17,10,14,19,2,6,13,8,7,15,12,5,18,20
// 7,1,17,6,16,18,20,2,15,5,10,11,3,13,14,12,19,8,9,4
// 18,4,1,6,11,14,10,20,7,2,3,5,13,12,16,8,15,19,17,9