87 lines
1.7 KiB
Lua
87 lines
1.7 KiB
Lua
-- Johnson–Trotter permutations generator
|
||
_JT={}
|
||
function JT(dim)
|
||
local n={ values={}, positions={}, directions={}, sign=1 }
|
||
setmetatable(n,{__index=_JT})
|
||
for i=1,dim do
|
||
n.values[i]=i
|
||
n.positions[i]=i
|
||
n.directions[i]=-1
|
||
end
|
||
return n
|
||
end
|
||
|
||
function _JT:largestMobile()
|
||
for i=#self.values,1,-1 do
|
||
local loc=self.positions[i]+self.directions[i]
|
||
if loc >= 1 and loc <= #self.values and self.values[loc] < i then
|
||
return i
|
||
end
|
||
end
|
||
return 0
|
||
end
|
||
|
||
function _JT:next()
|
||
local r=self:largestMobile()
|
||
if r==0 then return false end
|
||
local rloc=self.positions[r]
|
||
local lloc=rloc+self.directions[r]
|
||
local l=self.values[lloc]
|
||
self.values[lloc],self.values[rloc] = self.values[rloc],self.values[lloc]
|
||
self.positions[l],self.positions[r] = self.positions[r],self.positions[l]
|
||
self.sign=-self.sign
|
||
for i=r+1,#self.directions do self.directions[i]=-self.directions[i] end
|
||
return true
|
||
end
|
||
|
||
-- matrix class
|
||
|
||
_MTX={}
|
||
function MTX(matrix)
|
||
setmetatable(matrix,{__index=_MTX})
|
||
matrix.rows=#matrix
|
||
matrix.cols=#matrix[1]
|
||
return matrix
|
||
end
|
||
|
||
function _MTX:dump()
|
||
for _,r in ipairs(self) do
|
||
print(unpack(r))
|
||
end
|
||
end
|
||
|
||
function _MTX:perm() return self:det(1) end
|
||
function _MTX:det(perm)
|
||
local det=0
|
||
local jt=JT(self.cols)
|
||
repeat
|
||
local pi=perm or jt.sign
|
||
for i,v in ipairs(jt.values) do
|
||
pi=pi*self[i][v]
|
||
end
|
||
det=det+pi
|
||
until not jt:next()
|
||
return det
|
||
end
|
||
|
||
-- test
|
||
|
||
matrix=MTX
|
||
{
|
||
{ 7, 2, -2, 4},
|
||
{ 4, 4, 1, 7},
|
||
{11, -8, 9, 10},
|
||
{10, 5, 12, 13}
|
||
}
|
||
matrix:dump();
|
||
print("det:",matrix:det(), "permanent:",matrix:perm(),"\n")
|
||
|
||
matrix2=MTX
|
||
{
|
||
{-2, 2,-3},
|
||
{-1, 1, 3},
|
||
{ 2, 0,-1}
|
||
}
|
||
matrix2:dump();
|
||
print("det:",matrix2:det(), "permanent:",matrix2:perm())
|