Й n2pat($N, $len) построить $N-ki шаблон перестановки длины $len sub n2pat {

my $1 =1,

my $N = shift,

my $len = shift,

my ©pat,

while ($1 <= $len + 1) { # Ha самом деле просто while ($N) { push ©pat, $N % $1, $N = int($N/$i), $1++,

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

Фущсция п2регт вызывается с двумя аргументами: номером генерируемо!! не-рестановки (от О до N!, где N - размер Л!ассива) и индексом последнего элемента массива. Функция п2регт для расчета шаблона перестановки вызывает подпро1"]5ам-му n2pat. Затем шаблон преобразуется в перестановку целых чисел подпрограммой pat2peГШ. Шаблон представляет собой список вида (О 2 О 1 О), что означает: «Вырезать пулевой элемент, затем второй элемент оставпшгося списка, затем нулевой, первый и снова пулевой».

Пример 4.4. mjd-permute

#/usr/bin/perl -w

й m]d permute перестановка всех введенных слов use strict,

while (о) {

my ©data = split,

my $num permutations = factorial(scalar ©data) for (my $1=0, $1 < $num permutations $i++) {

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

print ©permutation\n ,

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

my ©fact = (1),

sub factorial($) { my $n = shift,

return $fact[$n] if defined $fact[$n], $fact[$n] = $n . factorial($n - 1)

> Смотри также-

Описание функций unshift и splice вperlfunc{\); рецепты 2.7; 10.3.

Пример 4.4 (продолжение)

return ©pat;

# pat2perm(©pat) : превратить шаблон, возвращаемый n2pat(), й в перестановку целых чисел, sub pat2perm {

my ©pat = © ,

my ©source = (0 .. $#pat);

my ©perm:

push ©perm, splice(©source, (pop @pat), 1) while ©pat, return ©perm;

» n2perm($N, $len) сгенерировать N-ю перестановку S объектов sub n2perm {

pat2perm(n2pat(© ));

Хэши

Выполнять линейный просмотр в ассоциативном массиве - все равно что пытаться забить кого-нибудь до смерти заряженным «Узи».

Ларри Уолл

Введение

Как люди, так и части компьютерных программ взаимодействуют между собой самым причудливым образом. Отдельные скалярные переменные похожи на отшельников, ведущих замкнутое существование в рамках собственной личности. Массив напоминает партию, где множество индивидуумов объединяется под именем харизматического предводителя. Где-то между ними расположилась удобная ниша, в которой живут совокупности связей «один-к-одному» - хэши. В старой документации по Perl хэши часто назывались ассоциативными массивами, но термин получается слишком длинным. Аналогичные структуры данных существуют и в других языках, где они обозначаются другими терминами - хэш-таблицы, таблицы, словари, отображения и даже а-списки, в зависимости от языка.

К сожалению, отношения хэшей являются не равными, а подчиненными - например, «Энди - начальник Ната»; «Кровяное давление пациента - 112/62» или «Название журнала с индексом ISSN 1087-903Х - The Perl Journal». Хэш всего лишь предоставляет удобные средства для получения ответов на вопросы типа: «Кто является начальником Ната?» или «Как называется журнал 1087-903Х»? Вы не сможете спросить «Чьим начальником является Энди?» Впрочем, поиску ответов на подобные вопросы посвящен один из рецептов этой главы.

Однако у хэшей есть свои преимущества. В Perl хэш является встроенным типом данных. Благодаря применению хэшей многие сложные алгоритмы сводятся к простой выборке значений. Кроме того, хэши предоставляют быстрые и удобные средства для построения индексов и таблиц просмотра. Если для простой скалярной переменной применяется идентификатор типа $, а для массива - @, то для хэшей используется идентификатор %.

Префикс % относится лишь к ссылкам на хэш в целом. Значение ключа представляет собой скалярную величину, поэтому для него используется символ $ (по