Home Index

1  Algorithms

2  Subsequences

List distinct subsequences of characters in a string

#!/usr/bin/perl
use strict;
use warnings;
#-----------------------------------------------------------------------------------#
# Written by: Kevin T. Duraj
#-----------------------------------------------------------------------------------#
my $string = "Bono";

my $subsequences = &get_subsequences($string);
my $formatted = $subsequences;
$formatted =~ s/\s+/, /g;
print "The subsequences are:\n" . $formatted . "\n\n";

my %hash = ();
my @array = split(" ", $subsequences );

print "The sorted unique subsequences:\n";
foreach(@array)
{
  print $_ . ", " if not exists $hash{$_};
  $hash{$_}++;
}
print "\n";

#-----------------------------------------------------------------------------------#
sub get_subsequences
{
    my $string = shift;
    my $len = length($string);
    my @array = split //, $string;

    my (@subseq0, @subseq1, @subseq2, @subseq3);
    my $temp;
    my $subsequences;

    push(@subseq0, $string);
    $subsequences = join(" ", @subseq0) . " ";

    for (my $i = 0 ; $i < $len ; $i++)
    {
        my $first  = $i;
        my $second = 0;

        foreach (@array)
        {
            if ($first != $second)
            {
                $temp .= $_;
            }
            $second++;
        }

        push(@subseq1, $temp);
        $temp = undef;
    }

    @subseq1 = sort { lc $a cmp lc $b } @subseq1;
    $subsequences .= join(" ", @subseq1) . " ";

    for (my $a = 0 ; $a < $len ; $a++)
    {
        for (my $b = $a ; $b < $len ; $b++)
        {
            if ($a != $b)
            {
                my $temp = substr($string, $a, 1) . substr($string, $b, 1);
                push(@subseq2, $temp);
            }
        }
    }

    @subseq2 = sort { lc $a cmp lc $b } @subseq2;
    $subsequences .= join(" ", @subseq2) . " ";

    foreach (@array)
    {
        push(@subseq3, $_);
    }

    @subseq3 = sort { lc $a cmp lc $b } @subseq3;
    $subsequences .= join(" ", @subseq3) . " ";

    return $subsequences;
}

#-----------------------------------------------------------------------------------#

Copyright © 1997-2012 Kevin T. Duraj, All rights reserved
Agoura Hills, California -  Saturday, 19 May 2012