Friday, April 03, 2015
A little snippet of permutations
I'm working on a little Lua project, and I found myself with a surprisingly hard problem. The task, take the following string:
one/{two three four five}/alpha/beta/{gamma delta epsilon}.c
and generate all possible permutations of the string with the words in the braces appearing once. In essence, generate the following list:
one/two/alpha/beta/gamma.c one/two/alpha/beta/delta.c one/two/alpha/beta/epsilon.c one/three/alpha/beta/gamma.c one/three/alpha/beta/delta.c one/three/alpha/beta/epsilon.c one/four/alpha/beta/gamma.c one/four/alpha/beta/delta.c one/four/alpha/beta/epsilon.c one/five/alpha/beta/gamma.c one/five/alpha/beta/delta.c one/five/alpha/beta/epsilon.c
Parsing the string into a usable format was trivial (code left to the reader—hint: LPeg). So, starting from the output of parsing:
{
"one/",
{
"two",
"three",
"four",
"five"
},
"/alpha/beta/",
{
"gamma",
"delta",
"epsilon",
},
".c"
}
Then … what?
You have to iterate through the main table, and at the same time, iterate through any subtables that might exist (anywhere from zero on up). It took me a while to come up with the code. I knew that there was an elegant way to do this, and by God, I was going to find it.
Several hours later, and:
-- ***************************************************************
--
-- Copyright 2015 by Sean Conner. All Rights Reserved.
--
-- This library is free software; you can redistribute it and/or modify it
-- under the terms of the GNU Lesser General Public License as published by
-- the Free Software Foundation; either version 3 of the License, or (at your
-- option) any later version.
--
-- This library is distributed in the hope that it will be useful, but
-- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
-- License for more details.
--
-- You should have received a copy of the GNU Lesser General Public License
-- along with this library; if not, see <http://www.gnu.org/licenses/>.
--
-- Comments, questions and criticisms can be sent to: sean@conman.org
--
-- ********************************************************************
-- ***********************************************************************
-- Lua 5.3 renamed the unpack() function to table.unpack(). So check for
-- Lua 5.3 and handle accordingly.
-- ***********************************************************************
if _VERSION == "Lua 5.3" then
unpack = table.unpack
end
-- ***********************************************************************
-- This will take an array of strings and tables, and return an iterator
-- that will return successive permutations of strings.
--
-- The table is unpacked into arguments, and the add() function will slowly
-- walk down the argument list, calling itself recursively to generate all
-- possible strings from the list of arguments and yield them one at a time.
--
-- The expand() function will create the coroutine and return a function
-- usable by the for keyword.
-- ***********************************************************************
function expand(list)
local function add(a,x,...)
-- ------------------------------------------------------------
-- if x is nil, then we've exhausted all the paramters and have
-- accumulated a string we can yield. So yield it up.
-- ------------------------------------------------------------
if not x then
coroutine.yield(a)
-- --------------------------------------------------------------
-- if x is a string, call ourselves with the contatenation of our
-- accumulator string with x, and the rest of the paramters
-- --------------------------------------------------------------
elseif type(x) == 'string' then
add(a .. x , ...)
-- ----------------------------------------------------------------------
-- otherwise, we have a table. So iterate through the table, calling
-- ourselves each time with an updated accumulator value and the rest of
-- the parameters.
-- ----------------------------------------------------------------------
elseif type(x) == 'table' then
for i = 1 , #x do
add(a .. x[i], ...)
end
end
end
return function(co)
local okay,res = coroutine.resume(co)
return res
end,coroutine.create(function() add("",unpack(list)) end)
end
-- ***********************************************************************
-- The parsing of
--
-- one/{two three four five}/alpha/beta/{gamma delta epsilon}.c
--
-- into a table is left to the reader for an exercise. For right now, I'm
-- using a hardcoded table.
-- ***********************************************************************
test =
{
"one/",
{
"two",
"three",
"four",
"five"
},
"/alpha/beta/",
{
"gamma",
"delta",
"epsilon",
},
".c"
}
-- ***********************************************************************
-- And now, just expand the list, printing each result.
-- ***********************************************************************
for path in expand(test) do
print(path)
end
It's a decent example of recursion (where the trick is find the right base case and the reductions that lead to said base case). There might be non-recursive solutions, but I shudder at the potential complexity of such solutions.
