Two small programs. Just putting it out there for anyone who might be interested.

First one posted generates the lexicographic ordering of balanced parenthesis. Second one finds the least number of block moves to turn one string into another string.

Both are just initial sketches but I think they do what they should.

$ perl balanced.pl 3                                        
()()()
()(())
(())()
(()())
((()))
$ perl lcs.pl jamon hamon                                   
p=1     q=1     l=4
$ perl lcs.pl abcdef acdegh
p=0     q=0     l=1
p=2     q=1     l=3
[download]

#!/usr/bin/perl

=begin

Algorithm taken from:

TAOCP - D.Knuth
Vol 4 Fascicle 4 
Generating All Trees 
History of Combinatorial Generation
Algorithm P (Nested parenthesis in lexicographic order)

=cut        

use strict;
use warnings;
use v5.10;

my $n = shift || die "$!: need size";
my ( $l, $r ) = qw! ( ) !;
my $m;
( $m, my @a ) = init( $n, $m );

my $j;

while (1) {
    visit(@a);
    ( $m, @a ) = easy( $m, @a );
    next if ( $a[$m] eq $l );
    ( $m, $j, @a ) = findj( $m, @a );
    last if ( $j == 0 );
    ( $m, @a ) = incj( $m, $j, @a );
}

sub easy {
    my $m = shift;
    my @a = @_;
    $a[$m] = $r;
    if ( $a[ $m - 1 ] eq $r ) {
        $a[ $m - 1 ] = $l, $m--;
    }

    return $m, @a;
}

sub incj {
    my $m = shift;
    my $j = shift;
    my @a = @_;
    $a[$j] = $l;
    $m = 2 * $n - 1;
    return $m, @a;

}

sub findj {
    my $m = shift;
    my @a = @_;
    my $j = $m - 1;
    my $k = 2 * $n - 1;
    while ( $a[$j] eq $l ) {
        $a[$j] = $r, $a[$k] = $l, $j--, $k -= 2;
    }
    return $m, $j, @a;
}

sub init {
    my $n = shift;
    my $m = shift;
    $m = 2 * $n - 1;

    my @a;

    for my $k ( 1 .. $n ) {
        @a[ 2 * $k - 1, 2 * $k ] = ( $l, $r );
    }
    $a[0] = $r;
    return $m, @a;
}

sub visit {
    shift;
    print @_, "\n";
}
[download]

#!/usr/bin/perl

=begin

How many block moves does it take to transform one string to another?

algorithm taken from:
the string-to-string correction probem by Walter F. Tichy
ACM Transactions on Computer Systems Vol 2 No 4 Number 1984 p. 309-321

=cut

use strict;
use warnings;
use v5.10;

my @s = split //, shift || "shanghai rulez";
my @t = split //, shift || "sakhalin rulez";

# lengths

my $n = $#t;
my $m = $#s;

my ( $p, $q, $l ) = ( 0, 0, 0 );

while ( $q <= $n ) {
    ( $p, $l ) = f($q);

    printf( "p=%d\tq=%d\tl=%d\n", $p, $q, $l ) if ( $l > 0 );
    $q = $q + ( 1, $l )[ 1 < $l ];    # max(1,l) ... Perlmonks
}

sub f {
    my ($q)  = @_;
    my $pCur = 0;
    my $l    = 0;
    my $p    = 0;
    while ( ( $pCur + $l <= $m )
        and ( $q + $l <= $n ) )
    {

        my $lCur = 0;
        while ( ( $pCur + $lCur <= $m )
            and ( $q + $lCur <= $n )
            and ( $s[ $pCur + $lCur ] eq $t[ $q + $lCur ] ) )
        {
            $lCur++;
        }
        if ( $lCur > $l ) {
            $l = $lCur;
            $p = $pCur;
        }
        $pCur++;
    }
    return ( $p, $l );
}
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.