-- for readability in permgen
function swap( a, b ) return b, a end
-- recursive generation of all substrings, calls fn() with each
function permgen(a, n, fn)
if n == 0 then fn(a)
else
for i = 1, n do
a[n], a[i] = swap(a[n], a[i])
permgen(a, n-1, fn)
a[n], a[i] = swap(a[n], a[i])
end
end
end
-- Generic Iterator for permutating a table's values
function permutations(a)
local n = #a
local co = coroutine.create(function() permgen(a, n, coroutine.yield) end)
return function ()
local code, ret = coroutine.resume(co)
return ret
end
end
-- combines two substrings by detecting a single common suffix/prefix
function combine( a, b )
if not a then return b end
for i = 1, b:len() do
local s = a..b:sub(-i)
if s:sub(-b:len())==b then return s end
end
return a..b
end
-- compress a string by substring combination
function compress( ... )
local s
for i = 1, select("#", ...) do
s = combine( s, select( i, ... ) )
end
return s
end
-- shows all permutations, with stings compressed where possible
function generateCompressedList( words )
local list = {}
for v in permutations(words) do
table.insert( list, compress( unpack(v) ) )
end
table.sort( list, function(a,b)
if a:len() == b:len() then return a < b
else return a:len() < b:len() end
end )
return list
end
-- prints all compressed permutations of the 4 defined words
function main()
local words = { "testing", "ginger", "german", "minutes" }
local compressed = generateCompressedList( words )
for _, v in ipairs( compressed ) do
print(v)
end
end
-- Typo detection after all global functions declared
setmetatable(_G, {
__newindex=function(t,k,v) error("undeclared global var: "..k) end,
__index=function(t,k) error("undeclared global var:"..k) end
})
main()