كيف يمكنني توليد في جميع الأحوال من صفيف في بيرل؟

Question

ما هي أفضل (أنيقة وبسيطة وفعالة) وسيلة لتوليد كل التباديل n! من صفيف في بيرل؟

وعلى سبيل المثال، إذا كان لدي ل@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 : <لأ href = "http://learn.perl.org /faq/perlfaq4.html#How-do-I-permute-N-elements-of-a-list "يختلط =" نوفولو noreferrer ">" كيف يمكنني بدل ترتيب كذا العناصر N من قائمة؟ "

---

استخدم القائمة :: وحدة Permutor على كبان. إذا كانت القائمة في الواقع مجموعة، في محاولة وحدة خوارزمية :: بدل ترتيب كذا (أيضا 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;

ويوفر خوارزمية :: وحدة الحلقات أيضا وظائف NextPermute وNextPermuteNum التي تجد بكفاءة في جميع الأحوال فريدة من صفيف، حتى إذا كان يحتوي على قيم مكررة، تعديله في نفس المكان: إن عناصره هي في ترتيب فرز العكس ثم يتم عكس مجموعة، مما يجعل من فرزها، وترجع كاذبة. خلاف ذلك يتم إرجاع التقليب المقبل.

وNextPermute يستخدم ترتيب سلسلة وNextPermuteNum ترتيب رقمي، حتى تتمكن من تعداد كافة التباديل من 0..9 مثل هذا:

use Algorithm::Loops qw(NextPermuteNum);

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

Answer 2

وأقترح عليك استخدام قائمة :: Permutor :

use List::Permutor;

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

Answer 3

هل يمكن استخدام خوارزمية :: بدل ترتيب كذا و ربما <أ href ل = "http://www.foo.be/docs/tpj/issues/vol3_3/tpj0303-0010.html" يختلط = "noreferrer"> بالتكرار عبر التباديل (ووبيرل مجلة، خريف 1998) غير مثيرة للاهتمام قراءة بالنسبة لك.

Answer 4

وأوصي تبحث في لتوليد التباديل من أجل المعجمية ، وهو كيف لي مؤخرا حلها مشكلة 24 . عندما يكون عدد العناصر في مجموعة ينمو كبير، يصبح مكلفة لتخزين وفرز التباديل في وقت لاحق.

ويبدو List::Permutor، الذي اقترحه ماني، يولد عدديا التباديل تم فرزها. هذا ما كنت اذهب مع استخدام بيرل. دعونا نعرف كيف اتضح.

Answer 5

ونلقي نظرة على مكرر :: :: صفيف خشنة .

Answer 6

وجرب هذا،

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