Sepa

SEPA: A Simple, Efficient Permutation Algorithm Abstract Research in progress developing a fast algorithm which will find all possible permutations of a data set without the use of "helping" data structures or recursion. The SEPA Algorithm Three steps are needed to convert a data set to its next permutation. The first step is to find the key field for this permutation. The first field which changes between the two permutations is the key field. The key field in "abdca" as it becomes "acabd" (its next sorted order permutation) is the field containing the value 'b'. The key field can be determined by checking pairs of digits (or fields) starting from the rear (or right side) of the set. For each pair, if the left value of the pair is smaller than the right, then the field on the left is the key field. At this point all values to the right of the key field must be in sorted order from right to left (if not a field to the right would be the key field). If the key does not exist, the last permutation has been created. At this time, the data set is in reverse sorted order (from left to right). For clarification, those values to the right of the key field will be termed the "tail" of the set, while those to the left will be the "head". Note that the head, key, and tail will be different for each permutation. To find the next permutation in order, the key field must be exchanged with the smallest value in the tail which is larger than the key value. For example in the data set "abdca" the field with the value 'b' is the key, and the field containing the value 'c' has the smallest value in the tail which is larger than the key value. After swapping values, the set becomes "acdba". It is possible to find this value by comparing each value with the key value, starting at the end of the data set. The first value larger than the key value is the value to be exchanged with the key value. Notice that the tail (the 'c' is the key now) is still in reverse sorted order. This is important, because the last step is putting the tail into sorted order. Since the tail is in reverse sorted order, to sort it requires only a single loop, which works from both ends of the tail at the same time, swapping each pair of items while moving to the center of the tail. In this example, a character data set was used, but as stated before the logic behind this algorithm will work with other data sets, as long as there is a less than/greater than relationship among the data items. If all permutations are required, it is necessary that the original data set be the first permutation (exist in sorted order). 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). References [1]Robert Sedgewick. Algorithms (Second Edition). Addison-Wesley Publishing Company, August 1989. [2]Donald E. Knuth. The Art of Computer Programming (Volume 3 /Sorting and Searching). Addison-Wesley Publishing Company, 1973. [3]Jacques Arsac. Foundations of Programming. Academic Press Inc. (London) LTD. 1985. Listing 1 #include<STDIO.H> #include<STDLIB.H> void swap(char *s, int a, int b) { char temp=s[a]; s[a] = s[b]; s[b] = temp; } int permute(char *str, int len) { int key=len-1; int newkey=len-1; /* The key value is the first value from the end which is smaller than the value to its immediate right

*/

while( (key > 0) && (str[key] <= str[key-1]) ) { key--; } key--; /* If key < 0 the data is in reverse sorted order, which is the last permutation.

*/

if( key < 0 ) return 0; /* str[key+1] is greater than str[key] because of how key was found. If no other is greater, str[key+1] is used newkey=len-1; while( (newkey > key) && (str[newkey] <= str[key]) ) {

*/

}

newkey--;

swap(str, key, newkey); /* variables len and key are used to walk through the tail, exchanging pairs from both ends of the tail. len and key are reused to save memory */ len--; key++; /* The tail must end in sorted order to produce the next permutation.

*/

while(len>key) { swap(str,len,key); key++; len--; } }

return 1;

void main() { /* test data */ char test_string[] = "aabcd"; /* A short test loop to print each permutation, which are created in sorted order. do

{ printf("%s\n",test_string); } while( permute(test_string, strlen(test_string)) ); }

*/

{menu}

The Countdown QuickPerm Algorithm (Head):

(Formally Example_01) A complete permutation over a very large array is time consuming to say the least. Without a strategic plan, a permutation effort will be fruitless. In the algorithm presented below, exchanges are concentrated within the head of the target array such that one swap produces a new ordered list. Index values will not advance until all combinations are exhausted inside of the established range. Specifically, repeated access to an established upper index peak must be counted. Only when this count equals the value of the upper index in question can the upper index value proceed to the next available index level. Consider the following example regarding a prioritized list. Imagine that your house keys were lost while surfing the net at a friend's house. Where would you begin your search? Would your search begin a.) near the computer? b.) from an adjacent room? c.) at your house? d.) at a neighbor’s house? Odds are you would retrace your steps by first searching your pockets and the surrounding area repeatedly long before you would even search the neighbor’s house. Here choice "a" is intentionally placed first immediately followed by an ordered list of less likely choices (by degree). Choices very similar to these can be initially prioritized within an array before a permutation is even attempted. Frequently permutations begin with a known solution and attempt to improve upon agreeable ideas as permutable subsets. Simply stated, time management is vital when dealing with very large arrays or large character strings. Furthermore, assume that a fast computer can complete a permutation set using a 50element target array in exactly 10 seconds. It's also reasonable to assume this computer can complete a permutation set using a larger target array within a greater time period. Using the presented scenario above and the known factorial properties of a permutation, the following conclusions can be established: A permutation over a new 51-element array would complete in approximately: 10 Seconds * 51 = 510 Seconds or 8.5 Minutes A permutation over a new 52-element array would complete in approximately: 10 Seconds * 51 * 52 = 26520 Seconds or 442 Minutes or 7.37 Hours OR 8.5 Minutes * 52 = 442 Minutes or 7.37 Hours A permutation over a new 53-element array would complete in approximately: 10 Seconds * 51 * 52 * 53 = 1405560 Seconds or 16.27 Days A permutation over a new 54-element array would complete in approximately: 10 Seconds * 51 * 52 * 53 * 54 = 75900240 Seconds or 2.41 Years A permutation over a new 55-element array would complete in approximately: 10 Seconds * 51 * 52 * 53 * 54 * 55 = 4174513200 Seconds or 132.37 Years In the above scenario, an absolute solution can probably be identified within a 53-element array. Using an array with more than 53-elements would cause an unreasonable and

predictable wait. The QuickPerm algorithm presented below uses permutation subsets on the head of the target array. Often the target array a[N] is simply used to index large complex data structures. Here's the actual QuickPerm C++ algorithm for your review: QuickPerm - Head Permutations Using a Linear Array Without Recursion // NOTICE: #define N

Copyright 1991-2006, Phillip Paul Fuchs 12

// number of elements to permute.

Let N > 2

void QuickPerm(void) { unsigned int a[N], p[N+1]; register unsigned int i, j, tmp; // Upper Index i; Lower Index j for(i = 0; i < N; i++) // initialize arrays; a[N] can be any type { a[i] = i + 1; // a[i] value is not revealed and can be arbitrary p[i] = i; } p[N] = N; // p[N] > 0 controls iteration and the index boundary for i //display(a, 0, 0); // remove comment to display array a[] i = 1; // setup first swap points to be 1 and 0 respectively (i & j) while(i < N) { p[i]--; // decrease index "weight" for i by one j = i % 2 * p[i]; // IF i is odd then j = p[i] otherwise j = 0 tmp = a[j]; // swap(a[j], a[i]) a[j] = a[i]; a[i] = tmp; //display(a, j, i); // remove comment to display target array a[] i = 1; // reset index i to 1 (assumed) while (!p[i]) // while (p[i] == 0) { p[i] = i; // reset p[i] zero value i++; // set new index value for i (increase by one) } // while(!p[i]) } // while(i < N) } // QuickPerm()

QuickPerm - Function to Display Permutations (Optional) // NOTICE:

Copyright 1991-2006, Phillip Paul Fuchs

void display(unsigned int *a, unsigned int j, unsigned int i) { for(unsigned int x = 0; x < N; x++) printf("%d ",a[x]); printf(" swapped(%d, %d)\n", j, i); getch(); // press any key to continue... } // display()

The primary index controller array in the QuickPerm algorithm above is p[N], which controls iteration and the upper index boundary for variable i. This array is initialized to corresponding index values so that a simple countdown process can be utilized. The controller array is analogous to an incremental base N odometer, where digit p[0] is always zero, digit (or wheel) p[1] counts in base 2 or binary, digit p[2] counts in base 3, ..., and digit p[N] counts in base N+1. Initial values are assigned as follows: p[0] = 0 p[1] = 1 p[2] = 2

...

p[N] = N Initially the default upper index variable i is set to one as a reference to the second least significant odometer digit which in-turn is immediately reduced by one (a countdown process). Since the upper index variable is clearly odd, the default lower index variable j is assigned to the odometer digit referenced by the upper index which coincides to the value now stored in p[i] or zero. Both index variables are properly set and the first SWAP is called... Before another swap can take place, upper and lower index values must be recalculated based upon values stored in the base N odometer p[N]. Again the upper index begins at the binary digit p[1] and resets each consecutive ZERO digit to a corresponding index value (maximum digit). The upper index will settle upon the first odometer digit that is not zero then reduce the referenced digit by one (again a true countdown process). If the upper index is even, the lower index is assigned to the least significant odometer digit which coincides to the value stored in p[0] (or simply the lower index will remain at zero). Otherwise the lower index will be assigned to the actual odometer digit now referenced by the upper index. A SWAP is executed and this process continues until the upper index attempts to reference an odometer digit beyond the length of the linear permutable target in question. Notice the lower index always follows the upper index's lead. Observable modifications compared to the counting QuickPerm algorithm include the following: 1. Initializing all integers in the controller array to corresponding index values. 2. Decrement p[i] by one before the conditional assignment j = p[i] 3. While p[i] equals 0 DO reset p[i] to i then increment i by one. Using a nested while loop instead of a conditional if-else statement (as described in the counting QuickPerm algorithm) clearly lead to the development of a Meta-permutation class. Although this conditional optimization can be made regardless of the counting process utilized, the Meta-permutation class precludes such an optimization in order to return valid indices.

Fundamental Analysis of QuickPerm Above {Switch to Characters} Number of Objects to Permute (N)

a[N] Display of Initial Sequence

a[N] Display of Final Sequence

Total Number of Unique Combinations Produced (N!)

3

123

321

{Output}

2*3=6

4

1234

4123

{Output}

6 * 4 = 24

5

12345

52341

{Output}

24 * 5 = 120

6

123456

634125

120 * 6 = 720

7

1234567

7234561

720 * 7 = 5040

8

12345678

83456127

5040 * 8 = 40320

9

123456789

923456781

40320 * 9 = 362880

if N is even

1 2 3 . . . (N - 1) N

N 3 4 . . . (N - 2) 1 2 (N 1)

(N - 1)! * N = N!

if N is odd

1 2 3 . . . (N - 1) N

N 2 3 . . . (N - 1) 1

(N - 1)! * N = N!

A Permutation Ruler:

The graph below reflects how the value stored in the lower index variable j consistently reduces by one when the upper index variable i is odd, otherwise j is assigned a zero value. For each reference to j when i is odd, the lower index variable j will be assigned to the upper index variable “i – 1” then “i – 2” until the lower index variable j reaches zero. To control this iteration behavior, the value stored in the controller array p[i] is initialized to the same value stored in the upper index variable i (as mentioned above) then repeatedly reduced by one and assigned to the lower index variable j. This process continues until the lower index variable j reaches 0 then repeats. (Please note, the lower index variable j can also begin at zero and advance by one until the upper index value is reached.) This behavior is strictly controlled by the following statement: “IF i is odd then j = p[i] otherwise j = 0” Which in-turn translates to the following C++ statement: j = i % 2 * p[i];

(Click here to enlarge graph.)