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;

}

Page updated

Google Sites

Report abuse