in reply to
Finding Neighbours of a String

I have used the Math::Combinatorics to work out the combinations and permutations needed. The aim is to work out all of the ways in which a string of a certain hamming distance could be created rather than create all the possible permutations of the string and test them.

`use strict;
use warnings;
use Data::Dumper;
use Math::Combinatorics;
my $str = "TTTCGG";
my @str = split //, $str;
my $hammingDistance = 2;
# Calculate the total number of ways of getting the bases
my %bases;
my @baseopts = split //, 'ACGT' x $hammingDistance;
my $basecomb = Math::Combinatorics->new(count => $hammingDistance, dat
+a => [@baseopts], );
while(my @combo = $basecomb->next_combination){
my $permu = Math::Combinatorics->new(data => [@combo], );
while(my @permu = $permu->next_permutation){
$bases{join '', @permu}++;
}
}
# Make the list unique
my @baseperms;
push @baseperms, [split //, $_] foreach (keys %bases);
my %results;
my @n = (0 .. $#str);
# Calculate all the permutations of position that could give a change
# and work through the base combinations
my $poscomb = Math::Combinatorics->new(count => $hammingDistance, data
+ => [@n], );
while(my @combo = $poscomb->next_combination){
foreach my $bases (@baseperms){
my @newstr = @str;
@newstr[@combo] = @$bases;
$results{ join('', @newstr) }++;
}
}
print "$_ ", hd($_, $str), "\n" foreach (sort keys %results);
sub hd {
return ( $_[0] ^ $_[1] ) =~ tr/\001-\255//;
}
`