Combinations ( A, N, K, 0 );

}

Перестановки

Существует еще одна весьма непростая задача, которая хорошо решается с помощью ре-

курсии. Представьте, что к вам пришли Nгостей. Сколько существует различных способов рассадить их за столом?Сформулируем условие задачи математически. В массиве A[N]записаны целые числа.Надо найти все возможные перестановки этих чисел (в перестановку должны входить всеэлементы массива по 1 разу)Как и в предыдущем примере, предположим, что qэлементов массива (с номерами от 0 до q-1) уже стоят на своих местах. Тогда в позиции qможет стоять любой из неиспользованных элементов – их надо перебрать в цикле и вызвать рекурсивно эту же процедуру, увеличив на 1 количество установленных элементов. Чтобы не потерять никакой элемент, в цикле для

всех iот qдо N-1будем переставлять элементы A[i]и A[q], генерировать все возможные

комбинации, а затем менять их местами, восстанавливая исходный порядок.

Для обмена местами двух элементов массива будем использовать вспомогательную пере-

меннуюtemp.

void Permutations ( int A[], int N, int q )

{

Int temp;

if ( q == N ) // перестановка получена

PrintData ( A, N ); // вывод на экран

Else

for (int i = q; i <= N; i ++ ) {

temp = A[q]; A[q] = A[i]; A[i] = temp; // A[q]<->A[i]

Permutations(A, N, q+1); // рекурсивныйвызов

temp = A[q]; A[q] = A[i]; A[i] = temp; // A[q]<->A[i]

}

}