模組:Combination

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

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

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

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

將顯示為：

空集合
A
B
C
AB
AC
BC
ABC

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

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

將顯示為：

空集合
A
B
C
AB
AC
BB
BC
ABB
ABC
BBC
ABBC

而參數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}的子集合
空集合	A	B	C	AB	AC	BC	ABC

另可用參數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}的子集合
$\varnothing$	A	B	C	AB	AC	BC	ABC

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

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