PERL: БИБЛИОТЕКА ПРОГРАММИСТА


PERL: БИБЛИОТЕКА ПРОГРАММИСТА - стр. 146


@newitems = ©items,

@newperms = @perms,

unshift(@newperms, splice(@newitems, $i, 1)), permute([@newitems], Onewperms]),

Решение из примера 4.4, предложенное Марком-Джейсоном Доминусом (Mark-Jason Dominus), более элегантно и работает примерно на 25 % быстрее. Вместо того чтобы рассчитывать все перестановки, программа генерирует n-ю конкрет­ную перестановку. Элегантность проявляется в двух аспектах. Во-первых, в про­грамме удается избежать рекурсии, кроме как при вычислении факториала (ко­торый алгоритмом перестановок обычно не используется). Во-вторых, вместо перестановки реальных данных генерируется перестановка целых чисел.


4.19. Программа: permute   149

В программе для экономии времени использована методика запоминания. Ее суть заключается в том, что функция, Которая всегда возвращает конкретный ответ для конкретного набора аргументов, запоминает этот ответ. При следующем вы­зове с теми же аргументами дальнейшие вычисления уже не потребуются. Функ­ция factorial сохраняет ранее вычисленные значения факториала в закрытом мас­сиве @f act ( 10.3).

Функция n2perm вызывается с двумя аргументами: номером генерируемой пе­рестановки (от 0 до N!, где N — размер массива) и индексом последнего элемента массива. Функция n2perm для расчета шаблона перестановки вызывает подпрограм­му n2pat. Затем шаблон преобразуется в перестановку целых чисел подпрограммой pat2perm. Шаблон представляет собой список вида (0 2 0 1 0), что означает: «Вы­резать пулевой элемент, затем второй элемент оставшегося списка, затем нуле­вой, первый и снова пулевой».

Пример 4.4. mjd-permute

#' /usr/bm/perl -w

8 mjd_permute перестановка всех введенных слов

use strict,

while (о) {

my @data = split,

my $num_permutations = factorial(scalar @>data)

for (my $1=0, $i < $num_permutations $i++) {

my ©permutation = @data[n2perm($i, $#data)],

print @permutation\n ,

# Вспомогательная функция    факториал с запоминанием BEGIN  {

my ffact = (1), sub factonal($)  { my $r> = shift,




- Начало -  - Назад -  - Вперед -