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

Question

Какой лучший (элегантный, простой, эффективный) способ генерации всех 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"; 
} 

Answer 1

См perlfaq4: "How do I permute N elements of a 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; 

Вот небольшая программа, которая генерирует все перестановки всех слов на каждой строке ввода , Алгоритм воплощена в функции переставить() обсуждается в томе 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; 

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

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

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

Вы можете использовать Algorithm::Permute и, возможно, Iterating Over Permutations (The Perl Journal, Fall 1998) является интересным для чтения для вас.

Answer 3

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

use List::Permutor; 

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

Answer 4

Посмотрите на Iterator::Array::Jagged.

Answer 5

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

Должно быть достаточно чисто.

Answer 6

Я рекомендую посмотреть на algorithm for generating permutations in lexicographical order, как я недавно решил Problem 24. Когда количество элементов в массиве растет, оно становится дорогим для хранения и сортировки перестановок позже.

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

Answer 7

Perlmonks имеет несколько примеров: http://www.perlmonks.org/?node_id=503904

Answer 8

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

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