[Chinjut]

You can also simply iterate through permutations in lexicographic order, again taking O(n) time for each iteration. Specifically, given a_1, ..., a_n as the current permutation, to generate the next one, find the largest i for which a_i < a_{i + 1}. Then, find the largest j > i such that a_j > a_i. Swap the elements at indices i and j, then reverse the sub-array of elements at indices (i, n]. (The initial permutation should be the one with a_1, ..., a_n is ascending order, and the final permutation will have them in descending order (the case in which no i as described can be found))