Làm thế nào tôi có thể tạo tất cả các hoán vị của một mảng trong Perl?

Question

Cách tốt nhất (thanh lịch, đơn giản, hiệu quả) để tạo tất cả các hoán vị n! của một mảng trong perl là gì?

Ví dụ, nếu tôi có một mảng @arr = (0, 1, 2), tôi muốn đầu ra tất cả các hoán vị:

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

Nó có lẽ nên được một hàm trả về một iterator (lười biếng chậm đánh giá/vì n! có thể trở nên quá thì không thể lớn), vì vậy nó có thể được gọi như thế này:

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

Answer 1

Xem perlfaq4: "How do I permute N elements of a list?"

---

Sử dụng Danh mục :: Permutor mô-đun trên CPAN. Nếu danh sách thực sự là một mảng, hãy thử thuật toán :: Permute module (cũng trên CPAN). Nó được viết trong mã XS và rất hiệu quả:

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"; 
} 

Đối với thực hiện nhanh hơn, bạn có thể làm:

use Algorithm::Permute; 

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

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

Dưới đây là một chương trình nhỏ mà tạo ra tất cả các hoán vị của tất cả các từ trên mỗi dòng đầu vào . Thuật toán thể hiện trong các hoán vị() chức năng được thảo luận trong Tập 4 (vẫn chưa được công bố) của The Art of Computer Programming Knuth và sẽ làm việc trên danh sách bất kỳ:

#!/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; 

Các Thuật toán :: Module Loops cũng cung cấp NextPermute và Hàm NextPermuteNum tìm kiếm tất cả các hoán vị duy nhất của mảng, ngay cả khi nó chứa giá trị trùng lặp, sửa đổi tại chỗ: nếu các phần tử của nó theo thứ tự sắp xếp ngược thì mảng được đảo ngược, sắp xếp, và trả về false; nếu không thì hoán vị tiếp theo sẽ được trả về.

NextPermute sử dụng theo thứ tự chuỗi và NextPermuteNum trật tự số, vì vậy bạn có thể liệt kê tất cả các hoán vị của 0..9 như thế này:

use Algorithm::Loops qw(NextPermuteNum); 

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

Answer 2

bạn có thể sử dụng Algorithm::Permute và có thể Iterating Over Permutations (The Perl Journal, Fall 1998) là một chi thú vị cho bạn.

Answer 3

tôi đề nghị bạn sử dụng List::Permutor:

use List::Permutor; 

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

Answer 4

Hãy xem Iterator::Array::Jagged.

Answer 5

Nếu bạn muốn viết của riêng bạn, một thuật toán đệ quy s.t. nó sẽ chọn một mục ra khỏi mảng, và thực hiện cuộc gọi đến chính nó với mảng nhỏ hơn, cho đến khi mảng có kích thước một.

Nó phải khá sạch sẽ.

Answer 6

Tôi khuyên bạn nên xem số algorithm for generating permutations in lexicographical order, cách tôi đã giải quyết gần đây Problem 24. Khi số lượng các mục trong mảng phát triển lớn, nó trở nên đắt tiền để lưu trữ và sắp xếp hoán vị sau này.

Có vẻ như List::Permutor, được đề xuất bởi Manni, tạo ra các hoán vị được sắp xếp theo số lượng. Đó là những gì tôi muốn sử dụng với Perl. Hãy cho chúng tôi biết nó diễn ra như thế nào.

Answer 7

Perlmonks có một số ví dụ: http://www.perlmonks.org/?node_id=503904

Answer 8

Hãy thử điều này,

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"; 
} 

Output: Điều này sẽ cung cấp cho tất cả các kết hợp có thể có của các con số. Bạn có thể thêm logic để lọc ra các kết hợp không mong muố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