Home › Code Snippets

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

Posted July 14th, 2010 by s.r.chinn
in
Average rating
(0 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

On July 17th, 2010 ChemMeister says:

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

On July 17th, 2010 andyfaff says:

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,

On July 20th, 2010 s.r.chinn says:

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