A little snippet of permutations

Friday, April 03, 2015

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.

The Boston Diaries

Friday, April 03, 2015

A little snippet of permutations

Obligatory Picture

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous