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))
Another option is to use a factoradic[1]. The advantage with a factoradic is that you can index directly to any permutation without having to find its predecessor first.
4 comments
[ 0.23 ms ] story [ 14.6 ms ] thread[1]: http://en.wikipedia.org/wiki/Factorial_number_system