Syntactic Confectionery Delight PerlMonks

### generating permutations

 on Mar 29, 2017 at 17:20 UTC Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Sorry, I am very frustrated right now. I have spent the last six hours trying to come up with a simple perl program to list all permutations for the numbers from one to five (the use of cpan modules is not allowed for this exercise).

The well-known algorithm and code snippets in other languages can be found here:

One python implementation is very brief and almost understandable (though my python knowledge is even poorer than my perl knowledge):

```def permute(in_str, prefix=""):
if not len(in_str) :
print(prefix)
else:
for i in range(0, len(in_str)):

permute(in_str[:i] + in_str[i + 1:], prefix + in_str[i])
permute('12345')
The biggest problem is (even after reading man perlsub for over an hour), I just don't understand the calling syntax. My attempt is looking something like this (which generates a huge number of syntax errors and won't run).
```#!/usr/bin/perl -w
use strict;

my @array = 1..5;

while (permute @array)

sub permute
{
my @temp;
while ( \$#temp < \$#_)

{
my \$i;
for (\$i = \$#temp; \$i < \$#_; \$i++)

{
swap @_[\$i] @_[\$#temp];
permute;
swap @_[\$i] @_[\$#temp];
}
}

print \$_;
}

sub swap
{
my \$k;
my \$l;
my  \$temp;
\$temp = \$k;
\$k = \$l;
\$l = \$temp;
}

Can someone guide me in the right direction. Clever techniques are not important. What is important is that I understand what is going on.

Thank you (very much) in advance.

Replies are listed 'Best First'.
Re: generating permutations
by toolic (Bishop) on Mar 29, 2017 at 17:33 UTC
Start smaller. Here is one basic way to create and use the swap sub:
```use warnings;
use strict;

my @swaps = swap(2, 3);
print "@swaps\n";

sub swap {
my \$k = shift; # 1st arg
my \$l = shift; # 2nd arg
return \$l, \$k; # List of 2 args swapped
}

__END__

Prints:

3 2

Re: generating permutations
by BrowserUk (Patriarch) on Mar 29, 2017 at 19:00 UTC

Here's a brute force conversion of the python code you posted:

```#! perl -slw
use strict;

sub permute {
my( \$in, \$pre ) = ( @_, '' );
if( not length \$in ) {
print \$pre;
} else {
for my \$i ( 0 .. length( \$in ) - 1 ) {
permute(
substr( \$in, 0, \$i ) . substr( \$in, \$i+1 ),
\$pre . substr( \$in, \$i, 1 )
);
}
}
}

permute( '12345' );;

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice.
Thanks, again. With a few extra print statements, I am able to see exactly what it is doing.

A quick (I hope) follow up. How would I do a more general list - say all the permutations of (apple, banana, orange), or numbers that go into double digits?

Try this. It's a re-casting of the Python algorithm to operate on arrays:

```#! perl -slw
use strict;

sub permute3 {
my( \$in, \$pre ) = ( @_, [] );
return print join '-', @\$pre unless @\$in;
permute3(
[ @{ \$in }[ 0 .. \$_-1, \$_+1 .. \$#\$in ] ],
[ @\$pre, \$in->[ \$_ ] ]
) for 0 .. \$#\$in;
}

permute3( [ qw[ apple banana orange ] ] );;
__END__
C:\test>junk36
apple-banana-orange
apple-orange-banana
banana-apple-orange
banana-orange-apple
orange-apple-banana
orange-banana-apple

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice.

Here's a version that uses a separate array to mark when a item is used instead of building and destroying anon arrays.

```#!/usr/bin/perl

# http://perlmonks.org/?node_id=1186402

use strict;
use warnings;

my @items = qw( apple banana orange );
my @used;

sub permute
{
@_ == @items and return print "@_\n";
\$used[\$_]++ || permute(@_, \$items[\$_]), \$used[\$_]-- for 0 .. \$#items
+;
}

permute();
Re: generating permutations
by tybalt89 (Monsignor) on Mar 29, 2017 at 17:42 UTC
```#!/usr/bin/perl -l

# http://perlmonks.org/?node_id=1186402

use strict;
use warnings;

\$_ = 12345;

1 while print,
s/.*\K # find the last
(.) # digit such that
(.*) # there is a later (latest)
(.)(??{\$1 > \$3 and 'x'}) # digit greater than it
(.*) # and get rest
# swap those two digits ( \$1 & \$3 )
# then reverse everything after the first swapped digit
/ \$3 . reverse \$2.\$1.\$4 /xe

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1186402]
Approved by toolic
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?