# How to optimize this code to randomly shuffle a vector?

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;
};
``````

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

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