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. ...
Programming Development Portfolio of Kathleen Franz