Unnecessary complexity in generating labels

[JoannesJ]

trafficstars

As I understand it, the TrieBackTrackFilling method generates a simple static list and doesn't seem to benefit from the use of a Trie. I tried to do a straight forward implementation, and the result is a lot clearer and simpler:

function MinimizeKeystrokes:permutations(keys_str, n, opts)
  local keys = vim.split(keys_str, "")
  local keys_n = #keys

  local current_layer = vim.deepcopy(keys)
  local next_layer = {}
  local size = #current_layer

  while size < n do
    if #current_layer == 0 then
      current_layer = next_layer
      next_layer = {}
    end

    local base = current_layer[#current_layer]
    current_layer[#current_layer] = nil

    local expansion = vim.tbl_map(function(k) return base .. k end, keys)
    next_layer = vim.list_extend(expansion, next_layer)

    size = size + keys_n - 1
  end

  local perms = vim.tbl_map(
    function(label) return vim.split(label, "") end,
    vim.list_extend(current_layer, next_layer)
  )

  return vim.list_slice(perms, 1, n)
end

[hadronized]

It doesn’t really generate a static list. It generates a dynamic trie for as long as we generate sequences. Once the sequences are all generated, the trie is converted back to a simple list. That last operation might actually not be needed, but it would require changing a bit the way hinting works.

In the end, we can indeed simplify the algorithm if it generates the same output for the same inputs.

[JoannesJ]

It's been a while, but I don't remember this dynamic aspect being used. I thought the permutations method was the only way TrieBacktrackFilling was externally accessed, which results in a static list.