A Lua iterator for all permutations over the integers {1, 2, ..., n}.

perms.lua

-- This is meant to be used in a for loop, as in:
-- for perm in perms(n) do <stuff> end
function perms(n)
  local function iter(state, val)
    if not val then
      val = {}
      for i = 1, n do
        val[i] = i
      end
      return val
    end

    if n < 2 then return nil end

    -- j will be the rightmost index with val[j] < val[j + 1].
    local j = n - 1
    while val[j] > val[j + 1] do
      j = j - 1
      if j == 0 then return nil end  -- Done if val is {n, n - 1, ..., 1}.
    end

    -- k will be the rightmost index with val[k] > val[j].
    local k = n
    while val[k] < val[j] do
      k = k - 1
    end

    val[j], val[k] = val[k], val[j]

    -- Reverse val[j + 1] .. val[n].
    for i = 1, math.huge do
      local a, b = j + i, n - i + 1
      if a >= b then break end
      val[a], val[b] = val[b], val[a]
    end

    return val
  end
  return iter
end

This is based on Algorithm L from section 7.2.1.2 of Donald Knuth's Art of Computer Programming, volume 4A.