inv 再考

置換の表現には，リストタイプと巡回タイプとがあり，それぞれ積，逆元の実装に適していますが，今回のコードは根の置換という出自からリストタイプを利用しており，逆元の実装に工夫の余地がありました．現在公開中の inv は

inv(A):=map(second,sort(map("[",A,sort(A)),lambda([s,t],s[1]<t[1])))$

という sort ベースのもので

(%i3) L:random_permutation(makelist(i,i,1,10));
(%o3) [4,9,8,3,5,10,7,1,2,6]
(%i5) for j:1 thru 10^5 do inv(L)$
Evaluation took 19.6490 seconds (19.6760 elapsed) using 2073.668 MB.

といった具合でした．これを積（左作用）

mul(A,B):=map(lambda([s],A[s]),B)$

と同じく成分をインデックスと見做し，第 i 成分が s である入力のリストに対して，第 s 成分が i であるリストを出力とするもの

inv(A):=block([B,i],B:A*(i:0),for s in A do B[s]:i:i+1,B)$

に変更すると

(%i7) for i:1 thru 10^5 do inv(L)$
Evaluation took 4.1150 seconds (4.1320 elapsed) using 482.180 MB.

という結果となりました．