function spermutations(integer p, integer i)
-- generate the i'th permutation of [1..p]:
-- first obtain the appropriate permutation of [1..p-1],
-- then insert p/move it down k(=0..p-1) places from the end.
    integer k = mod(i-1,2*p)
    if k>=p then k=2*p-1-k  end if
    sequence res
    integer parity
    if p>1 then
        {res,parity} = spermutations(p-1,floor((i-1)/p)+1)
        res = res[1..length(res)-k]&p&res[length(res)-k+1..$]
    else
        res = {1}
    end if
    return {res,iff(and_bits(i,1)?1:-1)}
end function

for p=1 to 4 do
    printf(1,"==%d==\n",p)
    for i=1 to factorial(p) do
        ?{i,spermutations(p,i)}
    end for
end for