# 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.

- Next lexicographical permutation algorithm
- Print all permutations in sorted (lexicograpic) order
- the answer by Michal Forišek How would you explain an algorithm that generates permutations using loxicographic ordering?

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:

- (optional) sort given string or array
- find longest non-increasing suffix such that
`array[index] <= array[index+1]`

- identify the pivot index such that the first
`array[index] > array[index+1]`

- find the ceil (successor), the right most index such that
`array[pivot] < array[succ]`

- swap the pivot and successor, array[pivot] and array[succ]
- 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.Arrays;
public class AllPermutations {
static void sortedPermutations(char[] array) {
Arrays.parallelSort(array);
boolean isFinished = false;
int count = 0;
while (!isFinished) {
if (count !=0 && count % 10 == 0) System.out.println();
System.out.print((new String(array)) + " "); count++;
int index = array.length-2;
// find non-increasing suffix
while(index >= 0) {
if (array[index] <= array[index+1]) break;
index--;
}
if (index == -1) {
isFinished = true;
} else {
// the pivot is array[index]
// find the rightmost successor to the pivot in suffix
int succ = array.length-1;
while(array[succ] <= array[index]) succ--;
// swap the pivot and successor
char tmp = array[index];
array[index] = array[succ];
array[succ] = tmp;
// sort suffix
Arrays.parallelSort(array, index+1, array.length);
}
}
}
public static void main(String[] args) {
sortedPermutations("ABCDE".toCharArray());
}
}

The above code prints:

ABCDE ABCED ABDCE ABDEC ABECD ABEDC ACBDE ACBED ACDBE ACDEB ACEBD ACEDB ADBCE ADBEC ADCBE ADCEB ADEBC ADECB AEBCD AEBDC AECBD AECDB AEDBC AEDCB BACDE BACED BADCE BADEC BAECD BAEDC BCADE BCAED BCDAE BCDEA BCEAD BCEDA BDACE BDAEC BDCAE BDCEA BDEAC BDECA BEACD BEADC BECAD BECDA BEDAC BEDCA CABDE CABED CADBE CADEB CAEBD CAEDB CBADE CBAED CBDAE CBDEA CBEAD CBEDA CDABE CDAEB CDBAE CDBEA CDEAB CDEBA CEABD CEADB CEBAD CEBDA CEDAB CEDBA DABCE DABEC DACBE DACEB DAEBC DAECB DBACE DBAEC DBCAE DBCEA DBEAC DBECA DCABE DCAEB DCBAE DCBEA DCEAB DCEBA DEABC DEACB DEBAC DEBCA DECAB DECBA EABCD EABDC EACBD EACDB EADBC EADCB EBACD EBADC EBCAD EBCDA EBDAC EBDCA ECABD ECADB ECBAD ECBDA ECDAB ECDBA EDABC EDACB EDBAC EDBCA EDCAB EDCBA