Permutation Algorithms: Finding the Highest Discount Between Coupons

When trying to determine which coupons, in which order, can offer the highest amount of discount across a basket of products, a permutation algorithm is required.  A permutation algorithm calculates and returns all possible arrangements of a given set of items, where the order of those items are unique. 

In my research, I selected 4 permutation algorithms - Lexicographical, Heap's, Steinhaus-Johnson-Trotter-Even, and Recursive. They deliver perfectly unique permutations for my given set of coupons, but each does this in their own way. I picked these 4 to test for robustness and performance. All performed relatively quick, but do keep in mind - the use of a permutation algorithm is not for the faint of heart. It's big-O notation is usually O(2^n) or in this case O(n!), which means for just 4 items, 4 x 3 x 2 x 1 = 24 permutations; 5 items = 5 x 4 x 3 x 2 x 1 = 120 permutations. Therefore, it's a good idea to keep the number of items in your list as low as feasibly possible.

+++++++++++++++++++++++++++++++++++++

Lexicographical Permutation Algorithm

When something says "list 'A' is in lexicographical order", it means that all items in list 'A' are in alphabetical order, or in the case of numbers, in natural order. The idea behind this algorithm is exactly that. 

The version of this algorithm I've used creates an array of indicies, which represents each one of my given items in a list. This way, the items, themselves, can be as complex as they need to be, and be in whatever order they arrive. Their index values are what is being permuted. Then, the exact order of the indicies array will determine the permutation order of the items. It's logic goes something like this:

(note: the indicies array is "a"; and the values of "a" are the original index value when the indicies array was created; e.g a[0] = 0, a[1] = 1, etc.)

Step 1: get the lowest value j, from the right side of the array, where a[j] < a[j + 1]

Step 2: get the largest value k, from the right side of the array, where a[j] < a[k]

Step 3: r = a.length - 1 and s = j + 1, as long as r is greater than s, flip value at a[r] with value at a[s].

First returned permutation is the original order of the items. Then, my interpretation of this algorithm will basically permute items from the right side of the array first, before touching the items at the beginning of the array (on the far left. Here is an example output:

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]

Heap's Permutation Algorithm

Nothing to do with a specialized binary tree-based data structure with nodes sorted relative to its root, Heap's algorithm was created by B. R. Heap in the 1960s. Heap's algorithm permutes all possibilities of items, while keeping the last item to be changed out last. It does this by keeping track of the index of the last item swapped, how many times that item was swapped (during a given sequence) and looping through indicies from the beginning each time.

First returned permutation is the original order of the items. Here is an example output:

[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[4, 2, 1, 3]
[2, 4, 1, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[2, 1, 4, 3]
[1, 2, 4, 3]
[1, 3, 4, 2]
[3, 1, 4, 2]
[4, 1, 3, 2]
[1, 4, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[4, 3, 2, 1]
[3, 4, 2, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[3, 2, 4, 1]
[2, 3, 4, 1]

Steinhaus-Johnson-Trotter (with Even's speedup) Permutation Algorithm

The Steinhaus-Johnson-Trotter algorithm (SJT) creates its permutations by swapping out adjacent elements in a list. It requires the list to be in ascending order and, from right to left, swaps the largest number with the next adjacent number to the left. Once the largest number can no longer move left, the algorithm swaps the next largest number (far right) with its left adjacent number, and changes the direction of the largest number (in far left position), swapping it with all the numbers going back to the far right position. Hence, you will see a distinct zig-zag pattern with the largest number in the list.

Even's speedup to the algorithm is to note which direction each value in the list is going. A "mobile" number is a number that has a left adjacent number that is less than it. It's direction would be considered going "left" (which, in the beginning, all items are). Directions change when a number cannot be moved in its currently assigned direction. 

Best described by Ragavan N. (on his blog here), the steps to this algorithm is as follows:

Step #1: The algorithm works by placing the numbers 1…n in the increasing order and associating LEFT as the direction for each of them.

Step #2: Find the largest mobile integer and swap it with the adjacent element on its direction without changing the direction of any of these two.

Step #3: In doing so, if the largest mobile integer has reached a spot where it’s no more mobile, proceed with the next largest integer if it’s mobile (or with the next …). There’s a catch. Read step 4.

Step #4: After each swapping, check if there’s any number, larger than the current largest mobile integer. If there’s one or more, change the direction of all of them.

Step #5: The algorithm terminates when there are no more mobile integers.

First returned permutation is the original order of the items. Here is an example output:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
[1, 4, 3, 2]
[1, 3, 4, 2]
[1, 3, 2, 4]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[2, 4, 1, 3]
[2, 1, 4, 3]
[2, 1, 3, 4]

Recursive Permutation Algorithm

The recursive algorithm is not technically an algorithm, but more like a technique. Recursive here refers to the method that creates the permutations, being called recursively for each item in the list, with the rest of the items in the list. 

For example, consider a list with 3 items in an array:

Step #1: method is called with 3 items. it starts looping through the list, grabs the first item, and recursively calls itself with the other 2 items. So, the following permutations will start with ar[0].

Step #2: method is called with 2 items. it starts looping through the list, grabs the first item, and recursively calls itself with the last item. So, the following permutations will have its second item set to ar[1].

Step #3: method is called with 1 item. since there is only 1 item, it saves the entire sequence of values from Step #1 to now to the final list of permutations. call returns to Step #2.

Step #2.2: loops thru the list for the second time, grabs 2nd item in list; recursively calls itself with the first item. So, the following permutations will have its second item set to ar[2].

Step #3.2: method is called with 1 item. since there is only 1 item, it saves the entire sequence of values from Step #1 to now to the final list of permutations. call returns to Step #2.

Step #2.3: no more items to loop thru, so goes back to Step#1.

... and so on, until Step #1 goes loops thru all items in the list.

Last returned permutation is the original order of the items (the whole list generated gets inverted because of the recursive nature of this algorithm. Here is an example output:

[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 1, 3, 2]
[4, 1, 2, 3]
[3, 4, 2, 1]
[3, 4, 1, 2]
[3, 2, 4, 1]
[3, 2, 1, 4]
[3, 1, 4, 2]
[3, 1, 2, 4]
[2, 4, 3, 1]
[2, 4, 1, 3]
[2, 3, 4, 1]
[2, 3, 1, 4]
[2, 1, 4, 3]
[2, 1, 3, 4]
[1, 4, 3, 2]
[1, 4, 2, 3]
[1, 3, 4, 2]
[1, 3, 2, 4]
[1, 2, 4, 3]
[1, 2, 3, 4]

++++++++++++++++++++++++++++

After testing all 4 algorithms with the execution of returning the highest discount for a set of coupons, the recursive algorithm performed consistently quicker than the others (this was an unexpected surprise for me). And due to the required performance limitations of this module, a hard limit of 4 coupons was set to avoid timeout and/or out of memory issues.