Generalized backtrack generator for combinatorial objects

backtrack.lua

#!/usr/bin/env lua

-- For details: http://www2.seas.gwu.edu/~ayoussef/cs6212/backtracking.html

bins = {
    {1, 2, 3},
    {'a', 'b', 'c', 'd'},
    {'A', 'B'},
}
N = #bins

function backtrack()
    local r = 1 -- r is the tree level, or index of X
    local X = {} -- [1:N]; each element is an index into the corresponding element of bins

    for i= 1, N do
       X[i] = 0
    end

    while r > 0 do
       getnext(X,r) -- assigns to X[r] its next
       -- C-compliant value, if available.
       -- Otherwise, it re-initlizes X[r]
       -- to a0
       if X[r] == 0 then
          r = r - 1 -- backtrack to the previous level
       elseif r == N then
          display(X) -- a new complete solution
       else
          r = r + 1 -- move to the next level for X[r+1]
       end
    end
end

function getnext(X,r)
    X[r] = X[r] + 1 -- next tentative value

    while (X[r] <= #bins[r]) do
       if (bound(X, r) == true) then
          return
       else
          X[r] = X[r] + 1
       end
    end

    -- if getnext has not returned,
    -- that mean no C-compliant remaining
    -- value was found. Re-initialize X[r]
    X[r] = 0
end

function bound(X,l)
   -- /* X[1:l-1] are assigned C-compliant
   -- values. This function checks to
   --    see if X[l] is C-compliant */
   --    for i=1 to l-1 do
   --       if X[l] = X[i] then
   --          return(false);
   --          endif
   --          endfor
   
   return true
end

function display(X)
   for k,v in ipairs(X) do
      io.write(bins[k][v] .. ' ')
   end
   io.write "\n"
end


-- Do It!
backtrack()

Need to add some explanatory text and clean this up a bit.