# Indexing all elements of permutations $S_n$

I have this Table that gives all elements of $S_n$, I would like to know how to improve efficiency.

Table[i -> Part[Permutations[Table[n, {n, k}]], j, i], {j, k!}, {i, k}]


Already at k==7, this version is 85 times faster:

With[{k = 7}, Thread[Range[k] -> #] & /@ Permutations[Range[k]]] To make sure:

With[{k = 5}, Table[i -> Part[Permutations[Table[n, {n, k}]], j, i], {j, k!}, {i, k}]]
===
With[{k = 5}, Thread[Range[k] -> #] & /@ Permutations[Range[k]]]
(* True *)


The best I found so far is the following f3 (indeed very similar to the one of garej)

f1[k_] := Thread[Range[k] -> #] & /@ Permutations[Range[k]]
f2[k_] := With[{r = Range@k}, Thread[r -> #] & /@ Permutations@r]
f3[k_] := With[{r = Range@k},
f4[k_] := Transpose[Thread[# -> Permutations[Range[k]][[All, #]]] & /@ Range[k]];


Comparison:

data = Table[First@RepeatedTiming@f[k], {f, {f1, f2, f3, f4}}, {k, 7}]
ListPlot[data, PlotLegends -> {"march", 2, 3, "garej"},
PlotRange -> All, Joined -> True, PlotTheme -> "Detailed"]


{{9.5*10^-6, 0.000014, 0.000034, 0.00012, 0.00066, 0.0042, 0.033}, {9.3*10^-6, 0.0000126, 0.00002718, 0.00010, 0.00054, 0.0035, 0.028}, {0.000013, 0.000017, 0.000026, 0.0000614, 0.00030, 0.0022, 0.018}, {0.0000112, 0.0000188, 0.0000316, 0.000080, 0.00033, 0.0023, 0.02}} • why didn't you add my version to comparison? Mar 6 '16 at 11:43
• @garej sorry, I started improving the one of march; now added Mar 6 '16 at 12:05
• no problem - I've also made a shorter one with Inner Mar 6 '16 at 12:05

My favourite one is:

foo[k_]:= Inner[Rule, Range[k], Transpose @ Permutations[Range[k]], List]


This is also a fast option conceptually close to OP approach:

Transpose[Thread[# -> Permutations[Range[k]][[All, #]]] & /@ Range[k]];


Timing with Unlikely's comparison method for k = {7,8,9} on (i5, Win10, V10.30) Inner is a bit faster. : Edit Just for diversity:

MapIndexed[Last[#2] -> #1 &, Permutations[Range], {2}]