[lua]笔试-按字典序列出指指定的序列的位置

计算方法：

n的阶乘记为f(n), s为输入序列, sub(i)为s的i到n的子序列。A(i)为第i位对应的字母在子序列sub(i)中的字典顺序

N(s) = sum_{1,n} T(i)*(A(i) - 1) + 1

T(i)为i - 1的阶乘。

--[[

在线编程题1

比大小：

Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Problem Description:

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

abcdefghijkl

hgebkflacdji

gfkedhjblcia

1

302715242

260726926

计算方法：

n的阶乘记为f(n), s为输入序列, sub(i)为s的i到n的子序列。A(i)为第i位对应的字母在子序列sub(i)中的字典顺序

N(s) = sum_{1,n} T(i)*(A(i) - 1)  + 1

T(i)为i - 1的阶乘。

--]]

local s = "abcdefghijkl"

local function factorial(n)

	local f = 1

	for i=1,n do

		f = f * i

	end

	return f

end

function N(s)

	if type(s) ~= 'string' or #s == 0 then

		error('unexpected input')

	end

	local A = {a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8,i=9,j=10,k=11,l=12}

	local sum = 0

	local len = #s

	for i=1, len - 1 do

		local T = factorial(len - i)

		local a = string.sub(s,i,i)

		sum = sum + T * (A[a] - 1)

		for k, v in pairs(A) do

			if k > a then

				A[k] = A[k] - 1

			end

		end

		A[a] = 0

	end

	sum = sum + 1

	return sum

end

print(N("abcdefghijkl"))

print(N("hgebkflacdji"))

print(N("gfkedhjblcia"))

print(N("bacd"))

1

302715242

260726926