Void main(). Функция next_permut при каждом вызове формирует очередную перестановку элементов массива p и возвращает ее номер

{ int x[5];

for (int i = 0; i < 5; i++) x[i] = i+1;

permuts(x, 5, 0);

}

Функция next_permut при каждом вызове формирует очередную перестановку элементов массива p и возвращает ее номер. При исчерпании всех подстановок функция возвращает 0.

Алгоритм получения следующей перестановки поясним на примере. Пусть имеем перестановку

p = {4,2,3,5,6,1}.

Просматриваем элементы последовательности справа налево, начиная с предпоследнего. Находим первый из них, который меньше последующего. В нашем примере это элемент 3. Среди элементов, которые расположены справа от него находим наименьший элемент, который, в то же время, больше элемента 3. Таким явялется элемент 5. Меняем местами элементы 3 и 5. Получаем:

p = {4,2,5,3,6,1}.

Теперь все элементы, которые находятся правее, чем 5, упорядочиваем по возрастанию. Получаем окончательно:

p = {4,2,5,1,3,6}.

Следующая перестановка получена.

int next_permut(int* p, int n)

{ static int M=0;

M++; if (M == 1) return M;

int i, im, j, m;

for (i = n-2; i >= 0; i--)

{ if (p[i] < p[i+1]) { m = p[i+1]; im = i+1;

for (j = i+1; j < n; j++)

if (p[j] > p[i] && p[j] < m) { m = p[j]; im = j; }

break;

}

}

if (i < 0) return 0;

swp(p[i], p[im]);

sortup(i+1, n-1, p);

return M;

}

Пример использования функции next_permut:

Void main()

{ int i, N, A[5];

for (i = 0; i < 5; i++) A[i] = i+1;

while (N = next_permut(A, 5)) { printf("%3d ",N);

for (i = 0; i < 5; i++) printf("%2d ", A[i]);

puts("");

}

pause;

}