1 files changed, 65 insertions, 0 deletions
diff --git a/invperm.icl b/invperm.icl
new file mode 100644
index 0000000..5494aa6
--- /dev/null
+++ b/invperm.icl
@@ -0,0 +1,65 @@
+module invperm
+
+/*
+Inverse Permutation.
+
+Inverts the permutation represented by the list InitPerm.
+When a permutation of the form (n,n-1,...,2,1) is inverted this
+algorithm runs in linear time. The average (and worst) case
+behavior is however quadratic (in the size of the permutation).
+
+Run the program with the Show Constructors option on (Application options)
+*/
+
+import StdInt, StdMisc
+
+/*	A permutation (Perm) is represented as a list of integers.
+	The resulting inverse permutation (TPerm) is built up as a list of
+	tuples (TElt) containing an elements and its index, sorted on index.
+*/
+::Perm		:== [Int]
+::Index_new	:== Int
+::TElt		:== (Index_new,Int)
+::TPerm		:== [TElt]
+
+//	The initial permutation.
+//	inverse: [10,12,17,7,1,11,19,18,3,8,4,6,5,14,15,16,2,9,13].
+
+InitPerm::Perm
+InitPerm = [5,17,9,11,13,12,4,10,18,1,6,2,19,14,15,16,3,8,7]
+
+//	InvPerm returns the inverse of the permutation p by means of calling Ip.
+
+InvPerm::Perm -> Perm
+InvPerm p =  Ip 1 [] p
+
+/*	Ip inverts a permutation (3rd arg) by using the i'th element of
+	the initial permutation as index for i, which becomes the element
+	of the inverse permutation ('imperative': ip[p[i]] := i). At the
+	end the indices have to be removed from the inverse by means of 
+	the function Strip.
+*/
+Ip::Index_new TPerm Perm -> Perm
+Ip i ip []		=  Strip ip
+Ip i ip [e:pr]	=  Ip (i + 1) (Update_new ip e i) pr
+
+
+/*	Update adds an element to a list of (index,value)-pairs (a TPerm)
+	that is sorted on index.
+*/
+Update_new::TPerm Index_new Int -> TPerm
+Update_new []			   i x			=  [(i,x)]
+Update_new [e=:(j,y) : ar] i x	| i<j	=  [(i,x), e : ar]
+										=  [e : Update_new ar i x]
+
+//	Strip removes the (superfluous) indices from the resulting permutation.
+
+Strip::TPerm -> Perm
+Strip [] 			=  []
+Strip [(i,x):ar]	=  [x : Strip ar]
+ 
+
+//	The Start rule: invert the initial permutation.
+
+Start::Perm
+Start = InvPerm InitPerm