The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2021 by Sean Conner. All Rights Reserved.