Last active
December 6, 2020 21:51
-
-
Save neutronscott/6ddc33d4d8840c5ad4b1f96dfadd36e3 to your computer and use it in GitHub Desktop.
my first lua
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--[[ Psuedo-code given in chapter: | |
NextPerm(p1, p2, ..., pn) | |
Let k be the largest index such that P(k) < P(k+1) | |
If no such k exists then (p1, p2, ..., pn) is the last permutation | |
Let j be the largest index such that P(j) > P(k) | |
Swap P(j) and P(k) | |
Reverse the order of P(k+1), ..., P(n) | |
--]] | |
function nextperm(inset) | |
local j, k = nil, nil | |
local set = { table.unpack(inset) } -- copy set instead of modifying | |
for i = #set - 1, 1, -1 do | |
if set[i] < set[i+1] then | |
k = i -- loop index is out-of-scope after break | |
break | |
end | |
end | |
-- already last perm | |
if k == nil then return {} end | |
for i = #set, k, -1 do | |
if set[i] > set[k] then | |
j = i | |
break | |
end | |
end | |
-- i don't think this can fail | |
if j == nil then return {} end | |
set[k], set[j] = set[j], set[k] | |
-- reverse order after k | |
for i = 1, (#set - k) / 2, 1 do | |
set[i+k], set[#set+1-i] = set[#set+1-i], set[i+k] | |
end | |
return set | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment