Next Permutation
Next Permutation
1. Просматриваем а1, ..., аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена.
2. Рассматриваем ai+1, ai+2, ..., an. Найдем первый с конца am больший ai и поменяем их местами.
3. ai+1, ai+2, ..., an переставим в порядке возрастания (для этого достаточно её переписать с конца).
4. Печатаем найденную перестановку.
5. Возвращаемся к пункту 1.
boolean nextPermutation(int[] array) {
// Find longest non-increasing suffix
int i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i])
i--;
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0)
return false;
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
int j = array.length - 1;
while (array[j] <= array[i - 1])
j--;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
int temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
// Reverse the suffix
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
// Successfully computed the next permutation
return true;
}