테이블이

Question

내 입력은 다음과 같은 형식의 테이블 규칙을 보존 채우

_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의 각 항목은, nil 또는 채워진 중 하나를 자체가 여덟 항목이 포함 pos 동안 필드 min, max 및 pos을 가지고 데이터. 항상 4 개의 항목이 _input에있는 것은 아닙니다. 더 많은 항목이나 더 적은 항목이있을 수 있습니다. 최종 테이블 pos로부터 데이터 아이템의 최소/최대 값 :

내 목표 _input에서 적절한 값으로 채워진 하나의 테이블을 생성하는 알고리즘을 작성하고 min/max 규칙 (즉 보존한다. 최종 출력에는 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 위 예에서는 전무하다. 가능한 항목은 Item2 및 Item3이므로
5을 입력 할 수 없습니다. Item2이 이미 최대 금액에 도달했으며 Item3이 최대 금액에 도달 할 필요가 없습니다. 가능한 항목 Item1 및 Item4이 이미 최대 값에 도달했기 때문에
8을 채울 수 없습니다.

이것은 지금까지 나의 접근 방식이지만 모든 규칙을 보존하지 않고 "잘못된"출력을 생성합니다. 또한 매번 동일한 입력으로부터 동일한 결과를 얻지 않기를 바랍니다.

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