模組:Combination

模块文档[查看] [编辑] [历史] [清除缓存]

本模組可以列出指定出現次數的集合中的所有子集合

• 例如母集合為{A, B, C}，其子集合可由下列語法列出：

語法{{#invoke:Combination|subset| A=1 | B=1 | C=1 | format = *{{{1}}}\n }}

將顯示為：

• 若母集合某元素出現不止一次{A, B, B, C}，例如B出現2次，其子集合可由下列語法列出：

語法{{#invoke:Combination|subset| A=1 | B=2 | C=1 |format=*{{{1}}}\n}}

將顯示為：

• 而參數format控制的是輸出格式，也可以將其改為表格輸出

例如語法：

{| class=wikitable style="border-collapse: collapse;table-layout: fixed;width: 80%; text-align:center;"
{{#invoke:Combination|subset|A=1|B=1|C=1| format = {{!}}{{{1}}}\n }}
|}

將顯示為：

集合{A, B, C}的子集合

• 另可用參數empty_set控制空集合的輸出

例如語法：

{| class=wikitable style="border-collapse: collapse;table-layout: fixed;width: 80%; text-align:center;"
{{#invoke:Combination|subset|A=1|B=1|C=1| empty_set = <math>\varnothing</math> |format={{!}}{{{1}}}\n}}
|}

將顯示為：

集合{A, B, C}的子集合

上述文档嵌入自Module:Combination/doc。 (编辑 | 历史)
编者可以在本模块的沙盒 (创建 | 镜像)和测试样例 (创建)页面进行实验。
本模块的子页面。

local p = {}

function p.getCombinationGenerator()
	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

return p