# Permutation

#### How bad naive implementation of generating permutation

Permutation is a well-known problem in mathematics as well as programming. If a set of three characters, {A, B, C}, its permutation is:

``````ABC, ACB, BAC, BCA, CAB, CBA
``````

Three characters generate six patterns, which is `3*2*1`, a factorial of its size.

The easiest implementation is a brute-force, recursing all. How many times will it repeat? The answer is a factorial of total number of given characters. Crap! In terms of Big-O complexity, the factorial is the worst. See Big-O Complexitiy Chart at Big-O Cheat Sheet. To generate only 10 letters of permutation, 3628800 times repetition must be done.

#### How to effectively find permutation

This is a famous problem, so it’s easy to find the solution for “how to effectively find/generate permutation.” As far as I googled, these three were the best.

Overall, above three take the same approach. The trick is lexicographical order. The lexicographical order is not the goal but is the way to effectively generates permutations. Above three use the lexicographical order to find next permutations one by one. When there’s no next permutation, all permutations are generated.

#### Permutation generation code

Steps of the algorithm are:

1. (optional) sort given string or array
2. find longest non-increasing suffix such that `array[index] <= array[index+1]`
3. identify the pivot index such that the first `array[index] > array[index+1]`
4. find the ceil (successor), the right most index such that `array[pivot] < array[succ]`
5. swap the pivot and successor, array[pivot] and array[succ]
6. reverse the suffix from array[pivot+1] to array[array.length-1] if the array has been sorted at step 1, sort suffix instead of reversing

The sorted version of permutation in Java will be something like this:

The above code prints:

```ABCDE ABCED ABDCE ABDEC ABECD ABEDC ACBDE ACBED ACDBE ACDEB