Предполагая, что мы говорим о лексикографическом порядке по переставляемым значениям, существует два основных подхода, которые вы можете использовать:
- преобразование одной перестановки элементов в следующую перестановку (как опубликовано ShreevatsaR) или
- непосредственно вычисляет
n -ую перестановку, считая n от 0 и выше.
Для тех (как я ;-), которые не говорят на С ++ как нативные, подход 1 может быть реализован из следующего псевдокода, предполагая, что индексирование массива с нулевым индексом слева направо, с нуля некоторая другая структура, такая как список, «оставлена как упражнение»; -):
1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
call the current element the pivot,
and stop scanning
1.2. if the left end is reached without finding a pivot,
reverse the array and return
(the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
to find the rightmost element larger than the pivot
(call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return
Вот пример, начинающийся с текущей перестановки CADB:
1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB
Что касается второго подхода (прямого вычисления n -ой перестановки), помните, что существует N! перестановок N элементов. Следовательно, если вы переставляете N элементов, первые (N-1)! перестановки должны начинаться с наименьшего элемента, следующие (N-1)! перестановки должны начинаться со второго наименьшего и т. Д. Это приводит к следующему рекурсивному подходу (снова в псевдокоде, нумерации перестановок и позиций от 0):
To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
permutation ( x mod (N-1)! )
of the elements remaining in A after position p is removed
Так, например, 13-я перестановка ABCD находится следующим образом:
perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
B (because there's only one element)
DB
ADB
CADB
Кстати, «удаление» элементов может быть представлено параллельным массивом логических значений, который указывает, какие элементы все еще доступны, поэтому нет необходимости создавать новый массив при каждом рекурсивном вызове.
Итак, чтобы перебрать перестановки ABCD, просто посчитайте от 0 до 23 (4! -1) и непосредственно вычислите соответствующую перестановку.