## 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.