An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order |
| |
| Affiliation: | 1. Department of Science and Mathematical Engineering, Faculty of Petroleum and Mining Engineering, Suez University, Egypt;2. Department of Geomatics, Computer Science and Mathematics, University of Applied Sciences Stuttgart, Germany;3. Department of Geology, Suez Canal University, Ismailia 41522, Egypt;4. Heidelberger Akademie der Wissenschaften; Geographisches Institut der Universität Tübingen, Germany;1. Instituto de Ciencias Aplicadas y Tecnología (ICAT), Universidad Nacional Autónoma de México, Circuito Exterior S/N, C. U., 04510, México City, Mexico;2. Facultad de Ciencias, Universidad Autónoma de San Luis Potosí, San Luis Potosí, SLP, 78000, Mexico;1. Department of Electronics and Communication Engineering, National Institute of Technology Durgapur, India;2. Department of Electronics and Communication Engineering, Indraprastha Institute of Information Technology Delhi, India;1. Key Laboratory of Instrumentation Science & Dynamic Measurement (North University of China), Ministry of Education, 030051, Taiyuan, China;2. Xi’an Jiaotong University, China |
| |
| Abstract: | A systolic algorithm is described for generating all permutations of n elements in lexicographic order. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory, and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. This is an improvement over the best previously known techniques in two respects: the algorithm runs on the (arguably) weakest model of parallel computation, and is cost optimal (assuming the time to output the permutations is counted). The algorithm is extended to run adaptively, i.e., when the number of available processors is other than n. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
