Как я могу сгенерировать все перестановки массива в Perl?

Какой лучший (элегантный, простой, эффективный) способ генерации всех перестановок n! массива в perl?

Например, если у меня есть массив @arr = (0, 1, 2), я хочу вывести все перестановки:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Вероятно, это должна быть функция, которая возвращает итератор (ленивая/отложенная оценка, потому что n! может стать настолько невероятно большой), поэтому ее можно вызвать следующим образом:

my @arr = (0, 1, 2);
my $iter = getPermIter(@arr);
while (my @perm = $iter->next() ){
    print "@perm\n";
}

Ответы

Ответ 1

См. perlfaq4: "Как переставить N элементы списка?"

Используйте модуль List:: Permutor в CPAN. Если список фактически является массивом, попробуйте модуль Algorithm:: Permute (также в CPAN). Он написан в коде XS и очень эффективен:

use Algorithm::Permute;

my @array = 'a'..'d';
my $p_iterator = Algorithm::Permute->new ( \@array );

while (my @perm = $p_iterator->next) {
   print "next permutation: (@perm)\n";
}

Для более быстрого выполнения вы можете сделать:

use Algorithm::Permute;

my @array = 'a'..'d';

Algorithm::Permute::permute {
    print "next permutation: (@array)\n";
} @array;

Здесь небольшая программа, которая генерирует все перестановки всех слов в каждой строке ввода. Алгоритм, реализованный в функции permute(), обсуждается в томе 4 (до сих пор неопубликованный) Knuth Art of Computer Programming и будет работать в любом списке:

#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
    my $code = shift;
    my @idx = 0..$#_;
    while ( $code->(@_[@idx]) ) {
        my $p = $#idx;
        --$p while $idx[$p-1] > $idx[$p];
        my $q = $p or return;
        push @idx, reverse splice @idx, $p;
        ++$q while $idx[$p-1] > $idx[$q];
        @idx[$p-1,$q][email protected][$q,$p-1];
    }
}


permute { print "@_\n" } split;

Модуль Algorithm:: Loops также предоставляет функции NextPermute и NextPermuteNum, которые эффективно обнаруживают все уникальные перестановки массива, даже если они содержат повторяющиеся значения, изменяя его на месте: если его элементы находятся в порядке сортировки по обратным адресам, тогда массив отменяется, сортируя его и возвращает false; в противном случае возвращается следующая перестановка.

NextPermute использует строковый порядок и порядковый порядок NextPermuteNum, поэтому вы можете перечислить все перестановки 0..9 следующим образом:

use Algorithm::Loops qw(NextPermuteNum);

my @list= 0..9;
do { print "@list\n" } while NextPermuteNum @list;

Ответ 2

Я предлагаю вам использовать List::Permutor:

use List::Permutor;

my $permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = $permutor->next() ) {
    print "@permutation\n";
}

Ответ 5

Я рекомендую посмотреть алгоритм для генерации перестановок в лексикографическом порядке, как я недавно решил Проблема 24. Когда количество элементов в массиве растет, оно становится дорогим для хранения и сортировки перестановок позже.

Похоже, что List::Permutor, который был предложен Манни, генерирует численные сортированные перестановки. Это то, что я хотел бы использовать с Perl. Сообщите нам, как это получается.

Ответ 7

Попробуйте это,

use strict;
use warnings;

print "Enter the length of the string - ";
my $n = <> + 0;

my %hash = map { $_ => 1 } glob "{0,1,2}" x $n;

foreach my $key ( keys %hash ) {
    print "$key\n";
}

Выход: Это даст все возможные комбинации чисел. Вы можете добавить логику для фильтрации нежелательных комбинаций.

$ perl permute_perl.pl 
Enter the length of the string - 3
101
221
211
100
001
202
022
021
122
201
002
212
011
121
010
102
210
012
020
111
120
222
112
220
000
200
110

Ответ 8

Если вы хотите написать свой собственный, рекурсивный алгоритм s.t. он выберет один элемент из массива и сделает вызов самому себе с меньшим массивом, до массива размера один.

Это должно быть довольно чисто.