Как реализовать комбинации хвост-рекурсивно? - PullRequest
Новая
       23

Как реализовать комбинации хвост-рекурсивно?

1 голос
/ 23 июня 2019

Я учу себя Луа, читая Программирование Иерусалимского на Луа (4-е издание) и выполняя упражнения. Упражнение 6.5 - это

Напишите функцию, которая принимает массив и печатает все комбинации элементов в массиве.

После этого лаконичного утверждения книга дает подсказку, которая ясно дает понять, что от него ожидают написать функцию, которая печатает все C ( n , m ) комбинации m элементов из массива n элементов.

Я реализовал функцию combinations, показанную ниже: 

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

Работает нормально, но не рекурсивно.

Может кто-нибудь показать мне хвостовую рекурсивную функцию, которая делает то же самое, что и combinations выше?

(для чего он стоит, я использую Lua 5.3.)

NB: Я понимаю, что упражнение не требует, чтобы функция была хвостовой рекурсивной. Это требование я добавил сам, из любопытства.

РЕДАКТИРОВАТЬ: Я немного упростил функцию, но удалил пару вложенных функций, которые не добавляли много.

Ответы [ 2 ]

1 голос
/ 25 июня 2019

Есть третий вариант, у которого нет змеи, которая ест свой хвост.Хотя рекурсия с использованием tail-вызовов не приводит к переполнению стека, я избегаю этого из личных предпочтений.Я использую цикл while и стек, который содержит информацию для каждой итерации.В цикле вы извлекаете следующую задачу из стека, выполняете работу, а затем помещаете следующую задачу в стек.Я чувствую, что это выглядит чище, и легче визуализировать вложение.

Вот как я бы перевел ваш код так, как написал бы: 

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

Вы можете использовать это, покатехника цикла стека / узла практически для любого рекурсивного метода.Вот пример, где он применяется для печати глубоко вложенных таблиц: https://stackoverflow.com/a/42062321/5113346

Моя версия, используя ваш пример ввода, дает тот же результат: 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.

Простите, если он не работает с другими пропущенными параметрами, потому что я не пытался найти ответ на упражнение, а просто переписал код в исходном посте.

0 голосов
/ 23 июня 2019

ОК, я думаю, что нашел один способ сделать это: 

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

Эта версия, я думаю, хвостово-рекурсивна.К сожалению, он не распечатывает результаты в таком хорошем порядке, как моя оригинальная нерекурсивная версия (не говоря уже о дополнительной сложности кода), но не может быть всего!

РЕДАКТИРОВАТЬ: Ну нет, один может иметь все!Приведенная ниже версия является хвостовой рекурсивной, и выводит свои результаты в том же порядке, что и исходная не хвостовая рекурсивная версия: 

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

Используются следующие вспомогательные функции: 

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

Пример: 

> 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

По иронии судьбы, эта версия достигает хвостовой рекурсии за счет реализации своего собственного стека, поэтому я не уверен, что она в конечном итоге будет лучше, чем нерекурсивнаяверсия ... Опять же, я предполагаю, что функция stack на самом деле живет в куче (верно?), потому что таблицы Lua передаются по ссылке (верно?), так что, возможно, это улучшение, в конце концов.(Пожалуйста, поправьте меня, если я ошибаюсь!)

...