0

Sorry if this question is oddly specific; I wasn't sure where else to ask it, though!

I'm working through some problems, and I've found the Fisher-Yates Shuffle, but I want to know if this first shuffle I thought of is uniform or not? I'm not the greatest with probability.. or math... Ha.

The idea is pretty simple; for as many elements as there are in the array, pick two at random and swap them with each other.

function inPlaceShuffle(arr) {
    const floor = 0,
          ceil = arr.length - 1;

    let i = arr.length;

    while (i > 0) {
        swap(arr, getRandom(floor, ceil), getRandom(floor, ceil));

        i--;
    }

    return arr;
}

function swap(arr, firstIndex, secondIndex) {
    const temp = arr[firstIndex];
    arr[firstIndex] = arr[secondIndex];
    arr[secondIndex] = temp;
}

function getRandom(floor, ceil) {
    floor = Math.ceil(floor);
    ceil = Math.floor(ceil);
    return Math.floor(Math.random() * (ceil - floor + 1)) + floor;
}
Zach Nagatani
  • 301
  • 1
  • 4
  • 13

1 Answers1

0

Note that every iteration of loop gives n^2 combinations of indexes for change, and n iterations give n^(2n) variants, but this value does not divide n! permutations evenly for n>2, so some permutations will have higher probability than others.

Clear example:
There are 729 results for 6 permutations of {1,2,3}, 729 / 6 = 121. 5, so probability of permutations varies.

MBo
  • 77,366
  • 5
  • 53
  • 86