146 Глава 4 • Массивы Пример 4.2. (продолжение)

$rows = int(($#clata+$cols) / $cols),

# Задать маску для ускорения вычислений $mask = sprintf( %%-%cls , $maxlen-1),

# Подпрограмма для обнаружения последнего элемента строки sub EOL { ($item+1) % $cols == О }

# Обработать каждый элемент, выбирая нужный фрагмент

# на основании позиции

for ($iteiii = О, $item < $rows « $cols, $item++) {

my $target = ($item % $cols) * $rows + int($iteiii/$cols)

my Spiece = sprintf($mask $target < ©data $data[$target] ),

Ipiece =~ s/\s+$ if EOL(), # Последний элемент не выравнивать

print Spiece,

print \n If EOL(),

# Завершить при необходимости print \n If EOL(),

# He переносится -- только для Linux sub getwinsize {

ray Iwinsize = \0 x 8,

my STIOCGWINSZ = 0x40087468,

If (loctKSTDOUT, STIOCGWINSZ, Swinsize)) {

(Srows, Scols, Sxpixel, Sypixel) = unpack( 84 , Swinsize), } else {

Scols = 80,

Наиболее очевидный способ вывести отсортированный список по столбцам - последовательно выводить каждый элемент списка, выравнивая его пробелами до определенной ширины. Когда вывод достигает конца строки, происходит переход на следующую строку. Но такой вариант хорош лишь тогда, когда строки читаются слева направо. Если данные должны читаться по столбцам, сверху вниз, приходится искать другое решение.

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

Затем программа входит в цикл, который выполняется для каждой входной записи. Однако порядок вывода неочевиден. Предположим, имеется список из девяти элементов:

Неправильно Правильно

12 3 14 7

4 5 6 2 5 8

7 8 9 3 6 9

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

Проблема

Вам никогда не требовалось сгенерировать все возможные перестановки массива или выполнить некоторый фрагмент для всех возможных перестановок? Например:

% echo man bites dog permute

dog bites man

bites dog man

dog man bites

man dog bites

bites man dog

man bites dog

Количество возможных перестановок для множества равно факториалу числа элементов в этом множестве. Оно растет чрезвычайно быстро, поэтому не стоит генерировать перестановки для большого числа элементов:

Размер множества Количество перестановок

Программа words производит все необходимые вычисления, чтобы элементы (1,4,7) выводились в одной строке, (2,5,8) - в другой и (3,6,9) - в последней строке.

Текущие размеры окна определяются вызовом loctl. Этот вариант прекрасно работает - в той системе, для которой он был написан. В любой другой он не подойдет. Если вас это устраивает, хорошо В рецепте 12.14 показано, как определить размер окна в вашей системе с помощью файла ioctl.pch или программы на С. Решение из рецепта 15.4 отличается большей переносимостью, однако вам придется установить модуль с CPAN.

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

Рецепт 15.4.

Соответственно, выполнение операции для всех возможных перестановок занимает много времени. Сложность факториальных алгоритмов превышает количество частиц во Вселенной даже для относительно небольших входных значений. Факториал 500 больше, чем десять в тысячной степени!

use Math Biglnt, sub factorial { my $n = shift, my $s = 1,

$s ♦= $n-while $n > 0, return $s,

print factorial(Math Biglnt->new( 500 )), +1220136...(1035 digits total)

Два решения, приведенных ниже, отличаются порядком возвращаемых перестановок.

Решение из примера 4.3 использует классический алгоритм списковых перестановок, используемый знатоками Lisp. Алгоритм относительно прямолинеен, однако в нем создаются ненужные копни. Кроме того, в решении жестко закодирован простой вывод перестановок без каких-либо дополнительных действий.

Пример 4.3. tdc-permute

й/sf/bin/perl -п

й tsc permute вывод всех перестановок введенных слов permute([split], []), sub permute {

my ©Items = ©{ $ [0] }, my ©perms = ©{ $ [1] }, unless (©Items) {

print ©perms\n , } else {

my(©newiteiiis,©newperms, $i), foreach $i (0 $й11етз) { ©newitems = ©items, ©newperms = ©perms,

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

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