Computing Permutation Encodings

Leino, K. Rustan M. (1994) Computing Permutation Encodings. Technical Report. California Institute of Technology. [CaltechCSTR:1994.cs-tr-94-10]

Full text available as:

Other (Adobe PDF (182KB))

Abstract

We consider some encodings of permutations of the first N natural numbers, discuss some relations among them and how one can be computed from others. We show a short proof of an existing efficient algorithm for one encoding, and present two new efficient algorithms for encoding permutations. One of these algorithms is constructed as the inverse of an existing algorithm for decoding, making it the first efficient permutation encoding algorithm obtained that way.

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	139
Deposited By:	Caltech Library System
Deposited On:	25 April 2001
Record Number:	CaltechCSTR:1994.cs-tr-94-10
Official Persistent URL:	http://resolver.caltech.edu/CaltechCSTR:1994.cs-tr-94-10
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record