Timing[perms=Permutations[Range[8]]; Position[perms, #][[1,1]]& /@ perms;]

P2N[0,{}]=0;
P2N[1, {1}]=0;
P2N[n_, l_] := (n-1)!(n-Position[l, n][[1,1]])+P2N[n-1, Drop[l, -1] /. n -> Last[l]];
N2P[0, 0] = {};
N2P[1, 0] = {1};
N2P[n_, k_] := Block[
{tau=Append[N2P[n-1, k~Mod~((n-1)!)], n], p=n-k~Quotient~((n-1)!)},
tau /. {n->tau[[p]], tau[[p]] -> n}
];
N2P1[0, 0] = {};
N2P1[1, 0] = {1};
N2P1[n_, k_] := Block[
{
tau=N2P1[n-1, k~Mod~((n-1)!)], p=n-k~Quotient~((n-1)!)
},
If[p==n,
Append[tau,n],
Append[tau /. tau[[p]] -> n, tau[[p]]]
]
];

ns=P2N[5,#]& /@ Permutations[Range[5]]

(N2P1[5, #]& /@ ns)===Permutations[Range[5]]

Timing[n=8; P2N[n, N2P[n, #]]& /@ Range[0,n!];]

Timing[n=8; P2N[n, N2P1[n, #]]& /@ Range[0,n!];]

Timing[n=9; P2N[n, N2P[n, #]]& /@ Range[0,n!];]

Timing[n=9; P2N[n, N2P1[n, #]]& /@ Range[0,n!];]