How to implement combinations tail-recursively?

Question

I'm teaching myself Lua by reading Ierusalimschy's Programming in Lua (4th edition), and doing the exercises. Exercise 6.5 is

Write a function that takes an array and prints all combinations of the elements in the array.

After this succinct statement the book gives a hint that makes it clear that what one is expected to do is to write a function that prints all the C(n, m) combinations of m elements from an array of n elements.

I implemented the combinations function shown below:

function combinations (array, m)

  local append = function (array, item)
    local copy = {table.unpack(array)}
    copy[#copy + 1] = item
    return copy
  end

  local _combinations
  _combinations = function (array, m, prefix)
    local n = #array
    if n < m then
      return
    elseif m == 0 then
      print(table.unpack(prefix))
      return
    else
      local deleted = {table.unpack(array, 2, #array)}
      _combinations(deleted, m - 1, append(prefix, array[1]))
      _combinations(deleted, m, prefix)
    end
  end

  _combinations(array, m, {})

end

It works OK, but it is not tail-recursive.

Can someone show me a tail-recursive function that does the same thing as combinations above does?

(For what it's worth, I am using Lua 5.3.)

NB: I realize that the exercise does not require that the function be tail-recursive. This is a requirement I have added myself, out of curiosity.

EDIT: I simplified the function slightly, but removing a couple of nested functions that were not adding much.

Alundaio · Answer 1 · 2019-06-25T04:38:45.913

There is a third option, one that doesn't have a snake eating it's tail. Although recursion with tail-calls don't lead to stack overflow, I avoid doing so out of personal preference. I use a while loop and a stack that holds the information for each iteration. Within the loop you pop the next task from the stack, do the work, then push next task onto the stack. I feel it looks cleaner and it's easier to visualize the nesting.

Here is how I would translate your code into the way I would write it:

function combinations(sequence, item)
    local function append(array, item)
        local copy = {table.unpack(array)}
        copy[#copy + 1] = item
        return copy
    end

    local stack = {}
    local node = { sequence, item, {} }

    while true do
        local seq = node[ 1 ]
        local itm = node[ 2 ]
        local pre = node[ 3 ]

        local n = #seq
        if itm == 0 then
            print(table.unpack(pre))
        elseif n < itm then
            -- do nothing
        else
            local reserve = {table.unpack(seq, 2, #seq)}
            table.insert(stack, { reserve, itm, pre })
            table.insert(stack, { reserve, itm-1, append(pre, seq[ 1 ]) })
        end

        if #stack > 0 then
            node = stack[ #stack ] -- LIFO
            stack[ #stack ] = nil
        else
            break
        end
    end
end

You can use this while-loop stack/node technique for just about any recursive method. Here is an example where it's applied to printing deeply nested tables: https://stackoverflow.com/a/42062321/5113346

My version, using your input example gives the same output: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5.

Forgive me if it doesn't work with other passed params because I didn't try to solve the answer to the exercise but rather just rewrite the code in your original post.

kjo · Answer 2 · 2019-06-24T07:56:47.463

OK, I think I found one way to do this:

function combinations (array, m)

  local dropfirst = function (array)
    return {table.unpack(array, 2, #array)}
  end

  local append = function (array, item)
    local copy = {table.unpack(array)}
    copy[#copy + 1] = item
    return copy
  end

  local _combinations
  _combinations = function (sequence, m, prefix, queue)
    local n = #sequence
    local newqueue
    if n >= m then
      if m == 0 then
        print(table.unpack(prefix))
      else
        local deleted = dropfirst(sequence)
        if n > m then
          newqueue = append(queue, {deleted, m, prefix})
        else
          newqueue = queue
        end
        return _combinations(deleted, m - 1,
                             append(prefix, sequence[1]),
                             newqueue)
      end
    end
    if #queue > 0 then
       newqueue = dropfirst(queue)
       local newargs = append(queue[1], newqueue)
       return _combinations(table.unpack(newargs))
    end

  end

  _combinations(sequence, m, {}, {})

end

This version is, I think, tail-recursive. Unfortunately, it does not print out the results in as nice an order as did my original non-tail-recursive version (not to mention the added complexity of the code), but one can't have everything!

EDIT: Well, no, one can have everything! The version below is tail-recursive, and prints its results in the same order as does the original non-tail-recursive version:

function combinations (sequence, m, prefix, stack)
  prefix, stack = prefix or {}, stack or {}

  local n = #sequence
  if n < m then return end

  local newargs, newstack
  if m == 0 then
    print(table.unpack(prefix))
    if #stack == 0 then return end
    newstack = droplast(stack)
    newargs = append(stack[#stack], newstack)
  else
    local deleted = dropfirst(sequence)
    if n > m then
       newstack = append(stack, {deleted, m, prefix})
    else
       newstack = stack
    end
    local newprefix = append(prefix, sequence[1])
    newargs = {deleted, m - 1, newprefix, newstack}
  end

  return combinations(table.unpack(newargs)) -- tail call

end

It uses the following auxiliary functions:

function append (sequence, item)
  local copy = {table.unpack(sequence)}
  copy[#copy + 1] = item
  return copy
end

function dropfirst (sequence)
  return {table.unpack(sequence, 2, #sequence)}
end

function droplast (sequence)
  return {table.unpack(sequence, 1, #sequence - 1)}
end

Example:

> combinations({1, 2, 3, 4, 5}, 3)
1   2   3
1   2   4
1   2   5
1   3   4
1   3   5
1   4   5
2   3   4
2   3   5
2   4   5
3   4   5

Ironically, this version achieves tail-recursion by implementing its own stack, so I am not sure it is ultimately any better than the non-tail-recursive version... Then again, I guess the function's stack actually lives in the heap (right?), because Lua's tables are passed around by reference (right?), so maybe this is an improvement, after all. (Please correct me if I'm wrong!)

How to implement combinations tail-recursively?

2 Answers2