listShuffle.lua

listShuffle.lua

function initListAndMatrix (numElements)
	local l, pos = {}, {}
	for i = 1, numElements do
		l[i] = i
		pos[i] = {}
		for j = 1, numElements do pos[i][j] = 0 end
	end
	return l, pos
end

function printlist (l)
	for i = 1, #l do io.write(l[i] .. ' ') end
	io.write('\n')
end

function printmat (m)
	for i = 1, #m do printlist(m[i]) end
end

function listUpShuffle (l)
	local lsz = #l
	if lsz <= 1 then return l end

	local lsz2 = math.floor(lsz/2)
	local l1, l2 = {}, {}
	for k = 1, lsz2     do l1[#l1+1] = l[k] end
	for k = lsz2+1, lsz do l2[#l2+1] = l[k] end

	l1 = listUpShuffle(l1)
	l2 = listUpShuffle(l2)

	local res = {}
	local i, j = 1, 1
	while i <= #l1 or j <= #l2 do
		local rem1, rem2 = #l1-i+1, #l2-j+1
		if math.random() < rem1/(rem1+rem2) then
			res[#res+1] = l1[i]
			i = i+1
		else
			res[#res+1] = l2[j]
			j = j+1
		end
	end
	return res
end

function listDownShuffle (l)
	local lsz = #l
	if lsz <= 1 then return l end

	local lsz2 = math.floor(lsz/2)
	local l1, l2 = {}, {}
	for i = 1, lsz do
		local rem1, rem2 = lsz2-#l1, lsz-lsz2-#l2
		if math.random() < rem1/(rem1+rem2) then
			l1[#l1+1] = l[i]
		else
			l2[#l2+1] = l[i]
		end
	end

	l1 = listDownShuffle(l1)
	l2 = listDownShuffle(l2)

	local res = {}
	for i = 1, #l1 do res[#res+1] = l1[i] end
	for i = 1, #l2 do res[#res+1] = l2[i] end
	return res
end

math.randomseed(os.time())

local params = {...}
local numIterations = #params >= 1 and params[1] or 1
local numElements   = #params >= 2 and params[2] or 8

local l, pos = initListAndMatrix(numElements)
print("Up shuffle bias matrix:")
for i = 1, numIterations do
	local r = listUpShuffle(l)
	for j = 1, #r do
		pos[r[j]][j] = pos[r[j]][j]+1
	end
end
printmat(pos)

local l, pos = initListAndMatrix(numElements)
print("Down shuffle bias matrix:")
for i = 1, numIterations do
	local r = listDownShuffle(l)
	for j = 1, #r do
		pos[r[j]][j] = pos[r[j]][j]+1
	end
end
printmat(pos)

$ luajit listShuffle.lua 1000000 8
Up shuffle bias matrix:
125016 125144 124882 124818 125291 125294 124918 124637
124860 125276 124983 124723 124767 125219 125039 125133
125416 124866 125365 125111 125188 124651 124632 124771
125377 125054 124694 124574 124784 125179 125239 125099
124294 124661 125026 125520 125071 125418 124893 125117
125371 125111 124880 124840 124967 124956 125051 124824
124856 125183 125213 125089 125271 124510 124695 125183
124810 124705 124957 125325 124661 124773 125533 125236
Down shuffle bias matrix:
124844 124439 124393 125274 125995 124938 125120 124997
124581 124667 125246 124975 125796 124310 125258 125167
125004 125706 124880 124677 124947 125168 124927 124691
124822 124563 125606 124705 124823 125099 124793 125589
125162 125040 124223 125352 124717 125169 125131 125206
125167 125286 126093 124844 124228 125132 124586 124664
125119 125179 125121 125094 124421 125305 124687 125074
125301 125120 124438 125079 125073 124879 125498 124612

$ luajit listShuffle.lua 1000000 11
Up shuffle bias matrix:
90499 90602 90882 91188 91092 90389 91288 91161 90808 91148 90943
90792 91185 91068 90667 90873 90913 91051 90797 91365 90851 90438
90580 91244 91197 90444 91380 91143 91062 90558 90952 90463 90977
91302 90277 90749 90672 91110 91179 90755 90588 91316 91277 90775
90874 90787 90657 90884 90790 91040 91059 90742 91356 90877 90934
91166 90819 90665 91025 90566 91176 91083 90896 90232 91081 91291
91106 90879 90847 91483 91141 91123 90859 90704 90332 90632 90894
91555 90984 90835 90869 90776 90991 90536 90619 90845 91238 90752
90547 91006 91019 90943 90419 91274 90587 91191 90940 91305 90769
91157 90772 91139 90869 91072 90535 90774 91375 90848 90290 91169
90422 91445 90942 90956 90781 90237 90946 91369 91006 90838 91058
Down shuffle bias matrix:
90857 90531 90984 91046 91166 90533 91263 91040 91005 90718 90857
91145 90834 90797 91268 90471 90624 90630 91328 90883 91457 90563
91142 91031 91339 90900 91448 90883 90634 90566 90861 90145 91051
91056 91180 91142 90382 90811 91242 91009 91144 90399 90979 90656
91168 91117 90771 91394 90928 90396 91034 90400 90910 90920 90962
90466 90498 90717 90867 90638 91596 91065 91469 91387 90965 90332
90750 91079 90865 90823 91492 90993 90985 90097 90886 90614 91416
91259 91112 90634 90128 90687 90743 91602 90811 90997 91254 90773
91126 90601 90935 90844 90438 91318 90690 91031 91082 90899 91036
90492 91154 90936 90700 90875 90828 90201 91012 90982 91464 91356
90539 90863 90880 91648 91046 90844 90887 91102 90608 90585 90998