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


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


Рецепт 15.4.

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

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

Размер множества

Количество перестановок

1

1

2

2

3

6

4

24

5

120

6

720

7

5040

8

40320

9

362880

10

3628800

11

39916800

12

479001600

13

6227020800

14

87178291200

15

1307674368000


148   Глава 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

й1/usr/bin/perl -п

# tsc_permute вывод всех перестановок введенных слов

permute([split], []),

sub permute {

my @items = (°>{ $_[0] }, my @perms = @{ $_[1] }, unless (@items) {

print @perms\n , } else {

my(@newitems,@newperms, $i),

foreach $i (0  Stfitems) {




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