順列の全列挙
与えられた配列の順列をすべて列挙するアルゴリズム。なお同じ値の要素が含まれている場合は重複する順列は無視する。 以下の手順で、与えられた配列の辞書順でつぎの配列を求めることができる。すなわち、$ \{1, 2, 3, 2, 1\}が与えられたら、$ \{1, 3, 1, 2, 2\}が返る。
1. 与えられた配列を$ aとする。右から見ていって、昇順になっている最初の要素$ a_iを見つける。つまり$ \, a_i \lt a_{i + 1}。そのような$ a_iがなければ、これより辞書順で大きな配列は存在しないので終了する。
2. $ j \gt iで$ a_i \lt a_jとなる最小の$ a_jを見つける。これは配列を右から見ていって、初めて$ a_j \gt a_iとなる$ jを探せばよい。なんとなれば、$ a_k \ge a_{k+1} \, (k \gt i)より。
3. $ a_iと$ a_jを交換（swap）する
4. $ i+1以降の部分配列、すなわち$ a[i+1:n-1]を逆順にする（reverse）。これは$ i+1以降の部分配列を昇順にソートすることに相当する。なぜならステップ3以前は$ a[i+1:n-1]は降順になっており、ステップ3の直後でも降順が保たれるからである。
ステップ4で逆順にすることと昇順にソートすることが等価になる証明
証明すべきは$ a_{i+1} \ge a_{i+2} \ge \ldots \ge a_{j-1} \gt a_i \ge a_{j+1} \ge \ldots \ge a_{n-1}すなわち(1) $ a_{j-1} \gt a_iと(2) $ a_i \ge a_{j+1}である。まずステップ3以前に$ a[i+1:n-1]が降順であったことから、$ a_{j-1} \ge a_jかつ$ a_j \ge a_{j+1}である。ステップ2で$ jを求めた条件から$ a_j \gt a_iであり、先程の降順の条件と合わせて$ a_{j-1} \ge a_j \gt a_iである。したがって(1)が証明できた。また$ jの条件から$ a_k \gt a_iとなる$ k \gt jは存在しない（もしあったら$ a_jが$ a_j \gt a_i\,(i \lt j \lt n)を満たす要素の最小という条件と矛盾する）。したがって$ a_i \ge a_{j+1}である。すなわち(2)が証明できた。
以上をJavaで書くとつぎのようになる。
code:java
public static boolean next(int[] a) {
final int n = a.length;
// ai < ai+1を満たす一番大きなiを探す int i = n - 2;
while (i >= 0 && ai >= ai + 1) i--; if (i < 0) return false; // なければaは降順にソート済みなので終了
// iより右側でaj > aiを満たす最小のajを探す。 // これは右端から見ていって最初に見つかったaj > aiを満たすjである。 int j = n - 1;
while (j > i && aj <= ai) j--; // iとjの位置の要素を交換
swap(a, i, j);
// ai+1:n-1を昇順にソートする。これは逆順にすることと等価。 j = n - 1;
i++;
while (i < j) swap(a, i++, j--);
return true;
}