SEPA: A Simple, Efficient Permutation Algorithm
source link: https://www.tuicool.com/articles/hit/a26N7jb
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Usual approaches to finding the permutations of a data set include the use of graphs as suggested by Robert Sedgewick[1] or using recursion as suggested by Jacques Arsac[3]. Both of these approaches have a common drawback they require helping data structures to perform the permutation. To create permutations using graphs, it is necessary to have data space for the data set to be permuted, as well as data space for the graph structures to perform the permutation. The recursive algorithm requires the overhead of recursive calls, or the use of a stack if implemented without recursion. These helping data structures can require as much space as the original data set. This paper discusses research in progress which will offer a new approach to the permutation problem, that retains the speed of the above algorithms, without requiring helping data structures.
Research
Upon inspecting character data sets as they permute, it was found that through a set of logical steps a set of character data can be permuted into its next permutation. It then becomes possible to find all permutations in sorted order by repeatedly calling the algorithm on the last output obtained. These same steps can be used on any data set in which the data have magnitude relationships. It was also discovered that each permutation could be created "in place", so no additional helping structure is required. Preliminary analysis reveal that the creation of each permutation has a worst case running time of O(n) and a much faster average running time.
The SEPA Algorithm
A quick review of the algorithm shows it is compose of three loops (an example in C is given as Listing 1). The first finds the key. The second finds the value to swap with the key. The third reorders the tail from reverse order to sorted order. A short analysis shows all three loops are bounded by the size of the data set, therefore the running time is bounded by O(n).
Future Research
The author with proceed to create in-depth proof showing the algorithm produces all permutations, as well as giving formal worst case, and average run time bound analysis. Representative implementations of both graph and recursive based algorithms will be giving with similar analysis as a comparison to this new approach. A memory constraint analysis will also be given for each of the algorithms.
Contributions
This algorithm's lack of helping data structures makes it a contribution to the field of Computer Science.
Acknowledgments
The author thanks Dr. Christopher Jones (Utah Valley State College) and Dr. Cory Barker (Brigham Young University-Hawaii Campus) for their support for this project.
References
Recommend
-
49
README.md GoAltdns
-
46
Intro Recap There are 2 approaches to explaining models
-
19
README.md dnstwist See what sort of trouble users can get in trying to type your domain name. Find similar-looking domains that adversaries c...
-
6
Cover all test cases with #permutationHi, weʼre arkency 👋
-
2
Permutation - Heap's Algorithm  This is a little bit of an experimentation that I did recently to figure out a reasonable code to get all possible permutations of a set of characters. So say given a set of characters "ABC"...
-
14
Sepa subject of 'significant cyber attack'Publishedduration20 hours agoimage copyrightGetty ImagesThe Scottish Environment Protection Agency says it is being subjected to a "si...
-
11
Sepa spends nearly £800,000 on cyber attack responseBy Andrew PickenBBC Scotland NewsPublished2 hours agoimage copyrightGetty ImagesScotland's env...
-
1
Sepa cyber attack recovery could take yearsPublished1 hour agoimage copyrightGetty ImagesScotland's environmental watchdog has said it could take years to fully recover from a...
-
2
Permutation group basis construction (Schreier–Sims algorithm) ...
-
3
Revolut connec...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK