Permutations by swapping: Difference between revisions

=={{header|Lua}}==

{{trans|C++}}

<lang Lua>

JT={

values={};

positions={};

directions={};

sign=1;

}

function JT:new(dim)

local n={}

setmetatable(n,{__index=self})

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

-- test

perm=JT:new(4)

repeat

print(unpack(perm.values))

until not perm:next()

</lang>

{{out}}

<pre>1 2 3 4

1 2 4 3

1 4 2 3

4 1 2 3

4 1 3 2

1 4 3 2

1 3 4 2

1 3 2 4

3 1 2 4

3 1 4 2

3 4 1 2

4 3 1 2

4 3 2 1

3 4 2 1

3 2 4 1

3 2 1 4

2 3 1 4

2 3 4 1

2 4 3 1

4 2 3 1

4 2 1 3

2 4 1 3

2 1 4 3

2 1 3 4</pre>