Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jan 3rd, 2012  |  syntax: Lua  |  size: 1.86 KB  |  views: 34  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. -- for readability in permgen
  2. function swap( a, b ) return b, a end
  3.  
  4. -- recursive generation of all substrings, calls fn() with each
  5. function permgen(a, n, fn)
  6.   if n == 0 then fn(a)
  7.   else
  8.     for i = 1, n do
  9.       a[n], a[i] = swap(a[n], a[i])
  10.       permgen(a, n-1, fn)
  11.       a[n], a[i] = swap(a[n], a[i])
  12.     end
  13.   end
  14. end
  15.  
  16. -- Generic Iterator for permutating a table's values
  17. function permutations(a)
  18.   local n = #a
  19.   local co = coroutine.create(function() permgen(a, n, coroutine.yield) end)
  20.   return function ()
  21.     local code, ret = coroutine.resume(co)
  22.     return ret
  23.   end
  24. end
  25.  
  26. -- combines two substrings by detecting a single common suffix/prefix
  27. function combine( a, b )
  28.   if not a then return b end
  29.   for i = 1, b:len() do
  30.     local s = a..b:sub(-i)
  31.     if s:sub(-b:len())==b then return s end
  32.   end
  33.   return a..b
  34. end
  35.  
  36. -- compress a string by substring combination
  37. function compress( ... )
  38.   local s
  39.   for i = 1, select("#", ...) do
  40.     s = combine( s, select( i, ... ) )
  41.   end
  42.   return s
  43. end
  44.  
  45. -- shows all permutations, with stings compressed where possible
  46. function generateCompressedList( words )
  47.   local list = {}
  48.   for v in permutations(words) do
  49.     table.insert( list, compress( unpack(v) ) )
  50.   end
  51.   table.sort( list, function(a,b)
  52.     if a:len() == b:len() then return a < b
  53.     else return a:len() < b:len() end
  54.   end )
  55.   return list
  56. end
  57.  
  58. -- prints all compressed permutations of the 4 defined words
  59. function main()
  60.   local words = { "testing", "ginger", "german", "minutes" }
  61.   local compressed = generateCompressedList( words )
  62.   for _, v in ipairs( compressed ) do
  63.     print(v)
  64.   end
  65. end
  66.  
  67. -- Typo detection after all global functions declared
  68. setmetatable(_G, {
  69.   __newindex=function(t,k,v) error("undeclared global var: "..k) end,
  70.   __index=function(t,k) error("undeclared global var:"..k) end
  71. })
  72.  
  73. main()