* * * * *
                                        
                        A little snippet of permutations
                                        
I'm working on a little Lua [1] 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 [2]). 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 [3] (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.

[1] http://www.lua.org/
[2] http://www.inf.puc-rio.br/~roberto/lpeg/
[3] http://en.wikipedia.org/wiki/Recursion

Email Sean Conner at sean@conman.org

.