[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