How to optimize this code to randomly shuffle a vector?

Developers Getting Started
1

The Fisher-Yates shuffle is a fast algorithm to randomly shuffle a vector. I have implemented it in Motoko but the final code is 4x the size of the pseudoceode. I ran out of ideas to reduce the SLoC. Maybe I’m missing some Array methods that could somehow make it all more efficient and elegant. any suggestion?

Pseudocode:

for (i=size; i>1; i--) {
   int p = random_bounded(i); // number in [0,i)
   swap(array+i-1, array+p); // swap the values at i-1 and p
}

Motoko:

    public func randomShuffle(vec: [Nat], seed: Nat): [Nat] {
      let fuzz = Fuzz.fromSeed(seed);  // external package 
      let vsize = vec.size();
      let vect = Array.thaw<Nat>(vec);
      for (j in Iter.range(0,vsize-3)) {
        let i: Nat = vsize - 1 - j;
        let p: Nat = fuzz.nat.randomRange(0, i);
        let aux = vect[i];
        vect[i] := vect[p];
        vect[p] := aux;
      };
      let vectf = Array.freeze<Nat>(vect);
      return vectf;
    };
2

Maybe this

  private func randomShuffle<A>(vect: [var A], seed: Nat): () {
      let fuzz = Fuzz.fromSeed(seed); 
      let vsize = vec.size();
      for (j in Iter.range(0,vsize -3)) {
        let i: Nat = vsize - 1 - j;
        let p: Nat = fuzz.nat.randomRange(0, i);
        let aux = vect[i];
        vect[i] := vect[p];
        vect[p] := aux;
      };
    };
2 Likes
3

Or this

 private func randomShuffle<A>(vect: [var A], seed: Nat) : () {
      let fuzz = Fuzz.fromSeed(seed); 
      for (i in Iter.range(0, vect.size() - 2)) {
        let p: Nat = fuzz.nat.randomRange(i, vect.size());
        let aux = vect[i];
        vect[i] := vect[p];
        vect[p] := aux;
      };
    };
2 Likes