Рекурсивный вызов не печатает ожидаемые комбинации строк в perl

Question

Ниже программа предназначена для печати всех возможных перестановок строки. Я попробовал это в Perl. Но выход не кажется ожидаемым. Может ли кто-нибудь помочь?

print "Enter string "; 
chomp($str = <STDIN>); 

$n = length($str); 

&combi($str, 0, ($n - 1)); 

sub combi { 
    $l = $_[1]; 
    $r = $_[2]; 
    if ($l == $r) { 
     print($_[0], "\n"); 
    } 
    else { 
     @char = split("", $_[0]); 

     for ($i = $l; $i <= $r; $i++) { 
      &swap($char[ $_[1] ], $char[$i]); 
      $res = join("", @char); 
      &combi($res, (($_[1]) + 1), $r); 
      &swap($char[ $_[1] ], $char[$i]); 
     } 
    } 
} 

sub swap { 
    $temp = $_[0]; 
    $_[0] = $_[1]; 
    $_[1] = $temp; 
} 

Выход программы:

Enter String: abc 
abc 
acb 

Answer 1

Я с трудом понимая код, но я думаю, что ваша проблема - вы пытаетесь сделать ей довольно тяжелый вес своего рода способ, но главное - вы не на самом деле «разматывая» хвост вашей рекурсии.

Точка рекурсивного алгоритма - это пересечение глубины, но сопоставление результатов.

Так что я бы подойти к вашей проблеме, как это:

#!/usr/bin/env perl 
use strict; 
use warnings; 

my $str = 'abcde'; 

sub combinations { 
    my ($string) = @_; 

    print "Starting combinations with \"$string\"\n"; 
    if (length($string) == 1) { 
     return ($string); 
    } 
    my @combinations; 
    for my $index (0 .. length($string) - 1) { 
     my @chars = split(//, $string); 
     my $firstletter = splice(@chars, $index, 1); 
     print "Keeping: $firstletter combining @chars\n"; 
     foreach my $combination (combinations(join("", @chars))) { 
      print "Got for @chars $combination\n"; 
      push(@combinations, $firstletter . $combination); 
     } 
    } 
    return (@combinations); 
} 

print join("\n", combinations($str)); 

У нас есть рекурсивная процедура, которая «данное» строки. Он выполняет итерацию каждой буквы в этой строке - выбирая «первую букву» и передавая оставшиеся буквы рекурсивному вызову, чтобы сделать то же самое.

Но тогда он «склеивает вместе» результаты вызова, чтобы составить список «результатов» - поскольку каждый «уровень» вызова должен генерировать ряд ответов, которые затем возвращаются к более высоким уровень вызова и т.д.

Примечание - Я также:

• включил strict и warnings - что очень важно при написании кода.
• не используется префикс & в подзаголовках. Это редко то, что вы хотите делать.
• не указан $_[0] - в качестве точки стиля следует избегать использования неявных переменных явно не более, чем необходимо. Назовите свои аргументы и дайте им имена, в которых ясно, что происходит.

Answer 2

Вы можете использовать модуль CPAN List::Permutor для печати всех возможных перестановок.

Например:

use List::Permutor; 
my $perm = new List::Permutor qw/ fred barney betty /; 
while (my @set = $perm->next) { 
    print "One order is @set.\n"; 
} 

Другой модуль Algorithm::Permute - Удобный и быстрый подстановка с объектно-ориентированного интерфейса.