Shuffle a string

Hi, If I have a string like

``````tt = "abcdefgh"
``````

How can I change the string so the order of the letters is random? I think other languages call it shufling but I couldn’t find anything in the docs…

```function setup()
str="abcdefghijklmnopqrstuv"
print(shuffle(str))
end

function shuffle(str)
randstr=""
while str~="" do
x=math.random(1,string.len(str))
randstr=randstr..string.sub(str,x,x)
str=string.sub(str,1,x-1)..string.sub(str,x+1)
end
return randstr
end

``````

You really do never sleep! Thanks natty

A variation on the same theme:

```function setup()
print(shuffle("abcdefghijklmnopqrstuvwxyz"))
end

function draw() background(0) end

function shuffle(strIn)
local n = #strIn
local strOut = {}
for i = 1, n do
local j = math.random(n)
strOut[i], strOut[j] = strOut[j] or strIn:sub(j, j),
strOut[i] or strIn:sub(i, i)
end
return table.concat(strOut)
end

``````

Interesting ideas!

@Ignatz’s code is good, but expensive on string creation (2n string created). Splitting to a table, randomising, and then concatenating would be cheaper.

@mpilgrem’s code is biased! It should be `local j = math.random(i,n)`. Here’s Jeff Attwood on why: http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html. And here’s where I describe how I learnt about the correct algorithm http://tex.blogoverflow.com/2011/08/do-the-knuth-shuffle/. I used this algorithm in the Anagrams program that comes with Codea. Now, I have it in a separate function:

``````function KnuthShuffle(n,odd)
local l
local o = 0
local p = {}
for k = 1,n do
p[k] = k
end
for k = 1,n-1 do
l = math.random(k,n)
if l ~= k then
p[k],p[l] = p[l],p[k]
o = 1 - o
end
end
if not odd and o == 1 then
p[1],p[2] = p[2],p[1]
end
return p
end
``````

This returns a permutation in the form of a table. If `odd` is nil or false then the resulting permutation is guaranteed to be even.

Yep, I knew using strings was expensive, but I figured he wasn’t randomising War and Peace, so he could probably afford a few microseconds for the sake of simple code.

Hello @Andrew_Stacey. Thank you for the references. Another attempt, then:

```function shuffle(strIn)
local strOut = {}
local n = #strIn
for i = 1, n do
strOut[i] = strIn:sub(i, i)
end
for i = n, 2, -1 do
local j = math.random(i)
strOut[i], strOut[j] = strOut[j], strOut[i]
end
return table.concat(strOut)
end

``````

What a great algorithm, @Andrew_Stacey!