Module:Combination

local p = {}

local getArgs, yesno

function p.getCombinationGenerator() local CombinationGenerator = { list = {}, nums = {}, count = 0, number_count={}, factors={}, factor_index={} } function CombinationGenerator:init(prime_factors,fill_count) self.count=fill_count self.nums = {} for first,second in pairs(prime_factors) do if first ~= 'has_err' then self.nums[#(self.nums) + 1] = first self.number_count[first] = 0 self.factors[first] = second end end table.sort(self.nums) for i = 1,#(self.nums) do self.factor_index[self.nums[i]]=i end end function CombinationGenerator:fill() if self.count <= 0 then return end local iterator = 1 local now_number = self.nums[iterator] if #(self.list) > 0 then iterator = self.factor_index[self.list[#(self.list)]] now_number = self.nums[iterator] end while #(self.list) < self.count do --test a number 'now_number' if self.number_count[now_number] < self.factors[now_number] then --if number 'now_number' can be put self.list[#(self.list) + 1] = now_number self.number_count[now_number] = self.number_count[now_number] + 1 else --if number 'now_number' can NOT be put if iterator + 1 > #(self.nums) then break end iterator = iterator + 1 now_number = self.nums[iterator] end end end function CombinationGenerator:checkNumberCount() if self.count <= 0 then return end for i = 1,#(self.nums) do self.number_count[self.nums[i]] = 0 end for i = 1,#(self.list) do self.number_count[self.list[i]] = self.number_count[self.list[i]] + 1 end end function CombinationGenerator:set(input) local result = {} if xpcall(function()_=#input pairs(input) end,function(_)end) == true then for key,value in pairs(input) do if tostring(tonumber(tostring(key)) or 0) == tostring(key) then result[key] = value end end self.list = result end self:checkNumberCount() end function CombinationGenerator:next() if #(self.list) > 0 then local iterator = self.factor_index[self.list[#(self.list)]] local now_number = self.nums[iterator] if iterator + 1 > #(self.nums) then return false end self.number_count[now_number] = self.number_count[now_number] - 1 iterator = iterator + 1 now_number = self.nums[iterator] self.number_count[now_number] = self.number_count[now_number] + 1 self.list[#(self.list)] = now_number return true end return false end function CombinationGenerator:copyListTo(newlist) if xpcall(function()_=#newlist pairs(newlist) end,function(_)end) == true then for key,value in pairs(self.list) do if tostring(tonumber(tostring(key)) or 0) == tostring(key) then newlist[key] = value end end end end function CombinationGenerator:findSubset(min_ele,max_ele) local outside_flag = true; local result = {} local end_val = tonumber(max_ele) or -1 if (tonumber(min_ele) or -1) <= 0 then self.count = 0 else self.count = min_ele end if end_val >= 0 and self.count > end_val then return result end

if #(self.nums) <= 0 then if self.count <= 0 then result[#result + 1] = {} end return result end

self:set({nil}) while outside_flag == true and (end_val < 0 or self.count <= end_val) do result, outside_flag = self:findCombination(nil, result, outside_flag) self.count = self.count + 1 end return result end function CombinationGenerator:findCombination(item_count, input_array, outside_flag) local result = input_array or {}

if item_count ~= nil then self.count = item_count end

if #(self.nums) <= 0 then if self.count <= 0 then result[#result + 1] = {} end return result end

if self.count <= 0 then self:set({nil}) result[#result+1] = {} self:copyListTo(result[#result]) else self:set({nil}) self:fill()

local middle_flag = true; while middle_flag == true do local inside_flag = true; while inside_flag == true do if (#(self.list) < self.count) then outside_flag = false break end result[#result+1] = {}

self:copyListTo(result[#result]) inside_flag = self:next() end

local backtrack_flag = true; while backtrack_flag == true do

local recursive_test = {value = tostring(table.concat(self.list,','))} local delete_num = self.list[#(self.list)] self.number_count[delete_num] = self.number_count[delete_num] - 1 self.list[#(self.list)] = nil recursive_test.count = #(self.list) if #(self.list) <= 0 then break end middle_flag = self:next()

self:fill()

local in_check,_ = mw.ustring.sub( tostring(table.concat(self.list,',')), 1, #tostring(recursive_test.value))

if ( tostring(in_check) == recursive_test.value ) == true then while #(self.list) > recursive_test.count do self.list[#(self.list)] = nil self:checkNumberCount(); end end

backtrack_flag = (#(self.list) < self.count) or #(self.list) <= 0 end if #(self.list) <= 0 then break end end end return result, outside_flag end return CombinationGenerator end

function p.subset(inputstr) --#invoke 支援 if not getArgs then getArgs = require('Module:Arguments').getArgs end local args = getArgs(inputstr, {parentFirst=true}) local t_vals = {} local t_args = {} for arg_name, arg_value in pairs( args ) do if tostring(mw.ustring.sub(arg_name,1,1)) == '\\' then if tostring(mw.ustring.sub(arg_name,2,2)) == '\\' then if (tonumber(arg_value)~=nil) then t_vals[tostring(mw.ustring.sub(arg_name,2))] = tonumber(arg_value) else t_args[tostring(mw.ustring.sub(arg_name,2))] = arg_value end else t_args[tostring(mw.ustring.sub(arg_name,2))] = arg_value end else if (tonumber(arg_value)~=nil) then t_vals[arg_name] = tonumber(arg_value) else t_args[arg_name] = arg_value end end end local empty_set = "空集合"; local format = "*{{{1}}}\n"; local no_output, min_val, max_val for arg_name, arg_value in pairs( t_args ) do if arg_name == "format" then format = arg_value or "*{{{1}}}\n"; elseif arg_name == "min" then min_val = tonumber(arg_value) or 0; elseif arg_name == "max" then max_val = tonumber(arg_value); elseif arg_name == "empty" or arg_name == "empty set" or arg_name == "empty_set" then empty_set = arg_value or "空集合"; elseif arg_name == "no_output" or arg_name == "no output" then no_output = arg_value; end end if not yesno then yesno = require('Module:Yesno') end no_output = yesno( no_output or 'no' ) format = mw.ustring.gsub(format or "*{{{1}}}\n", "%{%{%{.-%}%}%}", "%%s" ); local it = mw.ustring.find(format, "%%s", 1) if(not no_output) then if it == nil then format = format .. "%s" end end format = mw.ustring.gsub(format, "\\n", "\n") local result = {} local gened=p.getCombinationGenerator()

gened:init(t_vals,0) local combination = gened:findSubset(min_val,max_val)

local body = for i, result_str in pairs( combination ) do if(not no_output) then if #result_str <= 0 then body = body .. mw.ustring.gsub(format, "%%s", empty_set) else body = body .. mw.ustring.gsub(format, "%%s", table.concat(result_str,)) end else body = body .. format end end return body end

return p