Perl에서 배열의 모든 순열을 어떻게 생성 할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/635768

문제

모든 것을 생성하는 최고의 (우아하고 단순하고 효율적인) 방법은 무엇입니까 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: "목록의 요소를 어떻게 분출 시키나요?"

CPAN에서 목록을 사용하십시오. 목록이 실제로 배열 인 경우 알고리즘 :: 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 () 함수로 구현 된 알고리즘은 Knuth의 The Art of Computer Programming의 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;

다른 팁

나는 당신이 사용하는 것이 좋습니다 목록 :: 순수대:

use List::Permutor;

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

당신은 사용할 수 있습니다 알고리즘 :: 퍼 메이트 그리고 아마도 반복 오버 순열 (Perl Journal, 1998 년 가을)는 흥미로운 읽기입니다.

나는 an을 보는 것이 좋습니다 사전 순서로 순열을 생성하기위한 알고리즘, 이것이 내가 최근에 해결 한 방식입니다 문제 24. 배열의 항목 수가 커지면 나중에 순열을 저장하고 정렬하는 데 비용이 많이 듭니다.

보입니다 List::Permutor, Manni가 제안한 것은 수치 적으로 정렬 된 순열을 생성합니다. 그것이 Perl을 사용하여 갈 것입니다. 그것이 어떻게 나오는지 알려주십시오.

이 시도,

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
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top