Fisher-Yates Shuffle in place of vector

Software G'MIC
1

I’m trying to implement fisher-yates shuffle within G’MIC math parser:

foo:
eval "
 reference_vector=[0,1,2,3];
 repeat(3,k,
  swap(reference_vector[v(k,3)],reference_vector[3])
 );
 reference_vector;
 "

The test result:

3,0,2,1
0,3,1,2
0,3,1,2
0,1,2,3
0,1,3,2
3,0,1,2
3,1,0,2
0,3,1,2
3,1,2,0
0,3,2,1
3,1,0,2
3,0,1,2
3,1,0,2
0,1,3,2
3,1,0,2
3,0,1,2
0,3,1,2
0,1,2,3
0,1,3,2
0,1,2,3
0,3,1,2
3,1,2,0
0,3,2,1
0,3,2,1
3,0,1,2
0,1,2,3
0,1,2,3
0,1,2,3
3,1,0,2
0,3,2,1
0,3,1,2
0,1,3,2
0,1,3,2
0,1,3,2
0,1,3,2
0,3,1,2
0,1,3,2
3,1,2,0
0,3,1,2
0,3,1,2
3,1,2,0
0,1,3,2
3,1,2,0
0,1,2,3
0,3,1,2
0,1,3,2
0,3,2,1
0,3,2,1
3,1,2,0
0,1,2,3
0,1,2,3
0,3,2,1
3,0,2,1
3,1,0,2
0,1,2,3
3,1,2,0
3,1,2,0
3,1,2,0
3,0,2,1
0,1,3,2
0,3,1,2
0,1,3,2
0,2,3,1
0,1,2,3
0,1,2,3
0,3,2,1
0,1,3,2
0,1,3,2
0,3,2,1
0,1,3,2
3,1,0,2
3,0,1,2
0,1,3,2
3,1,2,0
0,3,1,2
0,3,1,2
0,3,2,1
3,1,2,0
0,3,1,2
0,3,1,2
0,3,2,1
0,1,2,3
0,1,3,2
0,3,1,2
0,2,3,1
0,1,2,3
0,2,3,1
0,1,3,2
0,3,1,2
0,1,3,2
0,2,3,1
0,2,3,1
0,1,3,2
3,0,2,1
3,0,2,1
0,1,3,2
3,1,2,0
3,1,0,2
0,3,1,2
0,3,2,1

The first thing I noticed is bias. The first number is either 0 or 3. Every time!

For now, my workaround is this:

# reference_vector is generated from $ +rep_permutations 4 permute cxyz echo {crop(#-1)}
eval "
 reference_vector= 
  [0,1,2,3
  ,0,1,3,2
  ,0,2,1,3
  ,0,2,3,1
  ,0,3,1,2
  ,0,3,2,1
  ,1,0,2,3
  ,1,0,3,2
  ,1,2,0,3
  ,1,2,3,0
  ,1,3,0,2
  ,1,3,2,0
  ,2,0,1,3
  ,2,0,3,1
  ,2,1,0,3
  ,2,1,3,0
  ,2,3,0,1
  ,2,3,1,0
  ,3,0,1,2
  ,3,0,2,1
  ,3,1,0,2
  ,3,1,2,0
  ,3,2,0,1
  ,3,2,1,0
  ];
 (reference_vector)[v(23)<<2,4];
 "
2 
foo :
  eval "
    shuffle(V) = (
      repeat (size(V),k, l = size(V) - k - 1; swap(V[l],V[v(0,l)]));
    );

    repeat (100,
      U = [ 0,1,2,3 ];
      shuffle(U);
      print(U);
    )"

seems to work better.

3

Alternatively :

    shuffle(V) = (
      repeat (size(V),k, swap(V[k],V[v(k,size(V) - 1)]));
    );

also works well (and is simpler).

1 Like