Как я могу сгенерировать все перестановки массива в Perl?
-
10-07-2019 - |
Вопрос
Какой самый лучший (элегантный, простой, эффективный) способ создания всех перестановок 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";
}
Решение
См. 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 (все еще не опубликовано) книги Кнута «Искусство компьютерного программирования» и будет работать с любым списком:
#!/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]=@idx[$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;
Другие советы
Я предлагаю вам использовать List :: Permutor :
use List::Permutor;
my $permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = $permutor->next() ) {
print "@permutation\n";
}
Вы можете использовать Algorithm :: Permute и, возможно, Итерация по перестановкам (The Perl Journal, осень 1998) - интересный читаю для вас. Р>
Я рекомендую взглянуть на алгоритм генерации перестановок в лексикографическом порядке , который как я недавно решил проблему 24 . Когда количество элементов в массиве становится большим, впоследствии становится дорого хранить и сортировать перестановки. Р>
Похоже, List :: Permutor
, который был предложен Манни, генерирует отсортированные по численности перестановки. Это то, что я бы использовал с использованием Perl. Дайте нам знать, как это получается.
Посмотрите на Iterator :: Array :: Jagged . р>
Попробуйте это,
use strict;
use warnings;
print "Enter the length of the string - ";
my $n = <> + 0;
my %hash = map { Попробуйте это,
$ 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
Вывод: это даст все возможные комбинации чисел. Вы можете добавить логику для фильтрации нежелательных комбинаций.
<*> => 1 } glob "{0,1,2}" x $n;
foreach my $key ( keys %hash ) {
print "$key\n";
}
Вывод: это даст все возможные комбинации чисел. Вы можете добавить логику для фильтрации нежелательных комбинаций.
<*>