填写table条保存规则

Question

我的输入是 table，格式如下：

_input = {
    ["Item1"] = {
        min = 1,
        max = 1,            
        pos = {
            [1] = nil,
            [2] = {--[[somedata]]},
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = nil,
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = {--[[somedata]]},
        },
    },
    ["Item2"] = {
        min = 1,
        max = 1,
        pos = {
            [1] = nil,
            [2] = nil,
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = {--[[somedata]]},
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = nil,
        },
    },
    ["Item3"] = {
        min = 1,
        max = 2,
        pos = {
            [1] = nil,
            [2] = {--[[somedata]]},
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = {--[[somedata]]},
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = nil,
        },
    },
    ["Item4"] = {
        min = 1,
        max = 3,
        pos = {
            [1] = {--[[somedata]]},
            [2] = {--[[somedata]]},
            [3] = {--[[somedata]]},
            [4] = nil,
            [5] = nil,
            [6] = nil,
            [7] = {--[[somedata]]},
            [8] = {--[[somedata]]},
        },
    },
}

_input中的每个条目都有字段min、max和pos，而pos本身包含八个条目，nil 或填充数据。 _input中并不总是给出四个项目。可以有更多项或更少项。

我的目标是创建一个生成单个 table 的算法，用 _input 中的适当值填充并保留 min/max 规则（即: 最终 table 中 pos 的 minimum/maximum 数据项数量。最终输出中必须有 min 项，并且可以有 max最终输出中的项目）。

鉴于上面的输入，输出可能如下所示：

_output = {
    [1] = {
        type = "Item4",
        data = {--[[the data from _input["Item4"].pos[1] ]]},
    },
    [2] = {
        type = "Item1",
        data = {--[[the data from _input["Item1"].pos[2] ]]},
    },
    [3] = {
        type = "Item4",
        data = {--[[the data from _input["Item4"].pos[3] ]]},
    },
    [4] = {
        type = "Item3",
        data = {--[[the data from _input["Item3"].pos[4] ]]},
    },
    [5] = nil,
    [6] = {
        type = "Item2",
        data = {--[[the data from _input["Item2"].pos[6] ]]},
    },
    [7] = {
        type = "Item4",
        data = {--[[the data from _input["Item4"].pos[7] ]]},
    },
    [8] = nil,
}

并非输出中的每个字段都必须填写：
5 和 8 在上面的例子中是零。
5 无法填写，因为唯一可能的项目是 Item2 和 Item3。 Item2 已经达到最大数量，Item3 不必达到最大数量。
8无法填写，因为可能的项目Item1和Item4都已经达到了最大数量。

到目前为止，这是我的方法，但它不保留所有规则并产生 "wrong" 输出。此外，我希望不要每次都从相同的输入中得到相同的结果。

local _output = {
    [1] = nil,
    [2] = nil,
    [3] = nil,
    [4] = nil,
    [5] = nil,
    [6] = nil,
    [7] = nil,
    [8] = nil,
}
for key in pairs(_input) do
    local _item = _input[key]

    for i=0,math.random(_item.min, _item.max),1 do
        -- I omit deepCopy() for readability
        local _possibleCopy = deepCopy(_item.pos)

        for i=1,8,1 do
            if _output[i] ~= nil then
                _possibleCopy[i] = nil
            end
        end

        local _possibleSlots = {}

        for i=1,8,1 do
            if _possibleCopy[i] ~= nil then
                _possibleSlots[#_possibleSlots+1] = i
            end
        end

        local _slot = _possibleSlots[math.random(1,#_possibleSlots)]

        if _slot then
            _output[_slot] = {
                type = key,
                data = _item.pos[_slot],
            }
        end
    end
end

Answer 1

math.randomseed(os.time())

local _input = {
    ["Item1"] = {
        min = 1,
        max = 1,
        pos = {
            [1] = nil,
            [2] = {--[[somedata]]},
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = nil,
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = {--[[somedata]]},
        },
    },
    ["Item2"] = {
        min = 1,
        max = 1,
        pos = {
            [1] = nil,
            [2] = nil,
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = {--[[somedata]]},
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = nil,
        },
    },
    ["Item3"] = {
        min = 1,
        max = 2,
        pos = {
            [1] = nil,
            [2] = {--[[somedata]]},
            [3] = nil,
            [4] = {--[[somedata]]},
            [5] = {--[[somedata]]},
            [6] = {--[[somedata]]},
            [7] = nil,
            [8] = nil,
        },
    },
    ["Item4"] = {
        min = 1,
        max = 3,
        pos = {
            [1] = {--[[somedata]]},
            [2] = {--[[somedata]]},
            [3] = {--[[somedata]]},
            [4] = nil,
            [5] = nil,
            [6] = nil,
            [7] = {--[[somedata]]},
            [8] = {--[[somedata]]},
        },
    },
}

local function deepCopy(tbl)
   -- insert your implementation here
end

local input_keys = {}        -- [input_key_idx] = input_key
local available = {}         -- [input_key_idx][1..8] = true/false
local avail_counters = {}    -- [input_key_idx][n] = count of available data items from 1 to n-1
local min, max = {}, {}      -- [input_key_idx] = min, max
local spent_data_items = {}  -- [input_key_idx] = number of data items included in _output
local selected_data_items = {} -- [1..8] = input_key_idx/0
local cache = {}
local _output

for k, v in pairs(_input) do
   table.insert(input_keys, k)
   local pos_avail = {}
   local avail_ctrs = {}
   local ctr = 0
   for i = 1, 8 do
      pos_avail[i] = not not v.pos[i]
      avail_ctrs[i] = ctr
      ctr = ctr + (pos_avail[i] and 1 or 0)
   end
   available[#input_keys] = pos_avail
   avail_counters[#input_keys] = avail_ctrs
   spent_data_items[#input_keys] = 0
   min[#input_keys] = v.min
   max[#input_keys] = v.max
   assert(ctr >= v.min and v.min <= v.max, "Solution does not exist")
end

local function enum_solutions(solution_no, n)
   -- returns the quantity of good selections
   n, solution_no = n or 8, solution_no or -1
   local cache_idx = n..";"..table.concat(spent_data_items, ";")
   local result = cache[cache_idx]
   if not result or solution_no >= 0 and solution_no < result then
      if n == 0 then
         -- found good selection (that satisfies the rules) in selected_data_items[1..8]
         if solution_no == 0 then
            _output = {}
            for n = 1, 8 do
               local key = input_keys[selected_data_items[n]]
               if key then
                  _output[n] = {type = key, data = deepCopy(_input[key].pos[n])}
               end
            end
         end
         result = 1
      else
         local must_be_selected = {}
         for input_key_idx = 1, #input_keys do
            if available[input_key_idx][n] and avail_counters[input_key_idx][n] + spent_data_items[input_key_idx] < min[input_key_idx] then
               table.insert(must_be_selected, input_key_idx)
            end
         end
         if #must_be_selected == 1 then
            local input_key_idx = must_be_selected[1]
            local spent = spent_data_items[input_key_idx]
            spent_data_items[input_key_idx] = spent + 1
            selected_data_items[n] = input_key_idx
            result = enum_solutions(solution_no, n-1)
            spent_data_items[input_key_idx] = spent
         elseif #must_be_selected == 0 then
            -- selecting nil for position n
            selected_data_items[n] = 0
            result = enum_solutions(solution_no, n-1)
            solution_no = solution_no - result
            for input_key_idx = 1, #input_keys do
               if available[input_key_idx][n] then
                  local spent = spent_data_items[input_key_idx]
                  if spent < max[input_key_idx] then
                     -- selecting _input[input_keys[input_key_idx]].pos[n] for position n
                     spent_data_items[input_key_idx] = spent + 1
                     selected_data_items[n] = input_key_idx
                     local delta_result = enum_solutions(solution_no, n-1)
                     result = result + delta_result
                     solution_no = solution_no - delta_result
                     spent_data_items[input_key_idx] = spent
                  end
               end
            end
         else
            result = 0
         end
      end
      cache[cache_idx] = result
   end
   return result
end

local number_of_solutions = enum_solutions()
assert(number_of_solutions > 0, "Solution does not exist")
print("There are "..number_of_solutions.." solutions exist")
-- generate 5 random solutions
for _ = 1, 5 do
   local k = math.random(number_of_solutions)
   print("Solution #"..k)
   enum_solutions(k-1)
   -- now _output is initialized with k-th variant of solution
   for i = 1, 8 do
      local v = _output[i]
      if v then
         print(i, v.type, v.data)
      else
         print(i, "-")
      end
   end
end

填写table条保存规则

Fill a table preserving rules

algorithm

lua

lua-table