Random (in-place) shuffle of input wave's elements

Average rating
(2 votes)

Here is a function that does an in-place permutation of an input wave's elements. I have also included a simple test function that I used to test 'shuffle()'. The code is adapted from several sources on the Web, and uses Igor's 'enoise()' function to generate the random permutation indices.

function shuffle(inwave)	//	in-place random permutation of input wave elements
	wave inwave
	variable N	=	numpnts(inwave)
	variable i, j, emax, temp
	for(i = N; i>1; i-=1)
		emax = i / 2
		j =  floor(emax + enoise(emax))		//	random index
// 		emax + enoise(emax) ranges in random value from 0 to 2*emax = i
		temp		= inwave[j]
		inwave[j]		= inwave[i-1]
		inwave[i-1]	= temp
	endfor
end
 
function test(npts, nshuffles)
	variable npts, nshuffles
	make/O/N=(nshuffles, npts) wave0 = q+1	//	2D  (trials) x (array size)
	make/O/N=(npts) wtemp					//	temporary column (trial) wave
	variable i
	for(i=0; i<nshuffles; i+=1)					//	shuffle each row
		wtemp = wave0[i][p]
		shuffle(wtemp)
		wave0[i][] = wtemp[q]
	endfor
	Make/O/N=(npts) wmean	//	mean of the trials column for each array 'bin'
	for(i=0; i<npts; i+=1)
		MatrixOp/O wdest = col(wave0,i)
		wmean[i] = mean(wdest)	//	in this test, should approach (npts+1)/2
	endfor
end

I think a faster way would

I think a faster way would be to use the Sort operation

Function Shuffle(InWave)
Wave InWave
Variable n=numpnts(InWave)
Make/o/N=(n) order=enoise(n) 
Sort order, InWave
End

I thought it would be faster

I thought it would be faster too, but it's not. I used startmstimer + stopmstimer, but it turns out using the inbuilt sort operation is a factor of two slower.

Thanks for the suggestion,

Thanks for the suggestion, and the timing test. I was not attracted to the sort method for mathematically pedantic reasons. It is conceivable (although extremely unlikely) that the random (continuous) sorting sequence might have some identical values. The crux of the shuffle algorithm is to change the available integer sample space after each sub-permutation to strictly avoid any kind of duplication problem. I might add that have also inspected the standard deviation of any given element after many trials, and it too agrees with theory. That said, had the sort method been significantly faster, I probably would use it if speed were an issue.

Back to top