Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Листинг 9.5. 
TSP.java (продолжение)
private static 
 
void 
allPermutationsHelper(T[] permutation, List 
permutations, 
int 
n) {
// Базовый случай — мы нашли новую перестановку, добавляем 
// ее и возвращаем
if 
(n <= 0) {
permutations.add(permutation);
return
;
}
// Рекурсивный случай — найдем больше перестановок, поменяв местами
T[] tempPermutation = Arrays.
copyOf
(permutation, permutation.length);
for 
(
int 
i = 0; i < n; i++) {
swap
(tempPermutation, i, n — 1); // переместим элемент из i в конец
// переместим все остальное, удерживая конечную константу
allPermutationsHelper
(tempPermutation, permutations, n — 1);
swap
(tempPermutation, i, n — 1); // возврат
}
}
Распространенный.шаблон.для.рекурсивных.функций,.которым.необходимо.со-
хранять.несколько.элементов.состояния.между.вызовами,.—.наличие.отдельной.
функции,.обращенной.наружу,.с.меньшим.количеством.параметров.и.которую.про-
ще.использовать..
allPermutations()
.—.это.более.простая.функция.(листинг.9.6).
Листинг 9.6. 
TSP.java (продолжение)
private static 
List permutations(T[] original) {
List permutations = 
new 
ArrayList<>();
allPermutationsHelper
(original, permutations, original.length);
return 
permutations;
}
Функция.
allPermutations()
.принимает.только.один.аргумент.—.массив,.для.кото-
рого.должны.быть.сгенерированы.перестановки..Чтобы.найти.эти.перестановки,.
функция.
allPermutations()
.вызывает.функцию.
allPermutationsHelper()
..Это.
избавляет.пользователя.функции.
allPermutations()
.от.необходимости.предостав-
лять.перестановки.параметров.и.значение.
n
.в.функции.
allPermutationsHelper()
.
Подход.с.возвратом.к.поиску.всех.представленных.здесь.перестановок.довольно.
эффективен..Для.поиска.каждой.перестановки.требуется.всего.две.перестановки.
в.массиве..Однако.можно.найти.все.перестановки.массива.с.помощью.всего.одной.
перестановки..Один.из.эффективных.алгоритмов,.выполняющих.эту.задачу,.—.
алгоритм.Хипа.(не.путать.со.структурой.данных.heap.(куча),.в.данном.случае.
Хип.—.это.имя.создателя.алгоритма)..Эта.разница.в.эффективности.может.быть.
важна.для.очень.больших.наборов.данных.(это.не.то,.с.чем.мы.здесь.имеем.дело).

---