Recursive call is not printing the expected combinations of a string in perl

Question

Below program is to print the all possible permutations of the string. I tried this in Perl. But the output is not seems to be the expected one. Could someone please help?

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

Output of the Program:

Enter String: abc
abc
acb

Answer 1

I'm having a hard time understanding your code, but I think your problem is - you're trying do to it quite a heavy weight sort of a way, but importantly - you're not actually 'unwinding' the tail of your recursion.

The point of a recursive algorithm is you traverse deep but collate the results.

So I'd approach your problem like this:

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

We have a recursive routine that's 'given' a string. It iterates each of the letters in that string - picking out the 'first letter' and handing the remaining letters to a recursive call to do the same thing.

But then it's 'sticking back together' the results of the call, to make a list of 'results' - since each 'level' of the call should be generating a number of answers, which it then returns to the higher level call, etc.

Note - I've also:

• turned on strict and warnings - which is really important when writing code.
• not used an & prefix in sub calls. That's rarely what you want to be doing.
• not referenced $_[0] - as a style point, you should avoid using implicit variables explicitly any more than necessary. Name your args, and give them names that's clear what's going on.