Finding String's Neighbors By Up To 2 Differing Positions

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

Dear Masters,
Given a seed string, I want to find its neighbors with at most differ in 2 positions. All the digits involve in generating string are only four (i.e. 0,1,2,3). This is the example for what I mean:

# In this example, 'first' column
are neighbours with only 1 position differ.
The rest of the columns are 2 positions differ

Seed = 000
100 110 120 130 101 102 103
200 210 220 230 201 202 203
300 310 320 330 301 302 303
010 011 012  013
020 021 022  023
030 031 032  033
001  
002  
003

Seed = 001
101 111 121 131 100 102 103   
201 211 221 231 200 202 203      
301 311 321 331 300 302 303      
011 010 012 013
021 020 022 023
031 030 032 033               
000
003
002     

Hence given a tag of length L
we will have 3*L + 9L(L-1)/2   neighbors
[download]

But why this code of mine fails to generate it correctly? Especially when the seed string is other than "000".

#!/usr/bin/perl -w
use strict;
use Data::Dumper;
use Carp;

# If possible we prefer not to use any CPAN module
# or regex. It's for my understanding


my $seed = $ARGV[0] || "000"; 
# Seed can be longer than 3 digits but always 0,1,2,3

for (my $i = 0; $i < length($seed); $i++) {

    # First loop is to generate 1 position differ
    for (my $bs=1; $bs<=3; $bs++) {

        my $bval = $bs;
        if ( substr($seed,$i,1) == $bs) {
            $bval = 0;

        }

        my $ns = $seed;
        substr($ns,$i,1,$bval);
        print "$ns\n";


        # Second loop for tags in 2 positions differ

        for (my $j=($i+1); $j < length($seed); $j++) {

            for (my $cs = 1; $cs<=3;$cs++) {

                my $cval = $cs;
                if (substr($ns,$j,1) == $cs) {
                    $cval = $cs;
                }

                 my $ns2 = $ns;
                 substr($ns2,$j,1,$cval);
                 print "\t$ns2\n";

            }
        }


    }
[download]

---
neversaint and everlastingly indebted.......

Comment on Finding String's Neighbors By Up To 2 Differing Positions Select or Download Code

Replies are listed 'Best First'.
Re: Finding String's Neighbors By Up To 2 Differing Positions by Limbic~Region (Chancellor) on Mar 27, 2009 at 13:46 UTC
neversaint, This is really simple when you leverage the power of CPAN. `#!/usr/bin/perl use strict; use warnings; use Algorithm::Loops 'NestedLoops'; use Text::Levenshtein 'fastdistance'; my $seed = $ARGV[0] \|\| '000'; my $iter = NestedLoops([([0..3]) x length($seed)]); while (my @list = $iter->()) { my $neighbor = join '', @list; print "$neighbor\n" if fastdistance($neighbor, $seed) < 3; }` [download] Update: Explanation of how the code works: Simply counts in base 4 and checks each number to see if edit distance is less than 3 from seed. Cheers - L~R	[reply] [d/l]
Re: Finding String's Neighbors By Up To 2 Differing Positions by Limbic~Region (Chancellor) on Mar 27, 2009 at 14:22 UTC
neversaint, Here is another solution that might should be more efficient than the one above. This solution only generates strings that are desired neighbor. Explanation for how it does that are in the comments. Read more... (2 kB) Cheers - L~R	[reply] [d/l]
Re: Finding String's Neighbors By Up To 2 Differing Positions by dsheroh (Monsignor) on Mar 28, 2009 at 16:48 UTC
Your inner loop is counting (and substituting) values from 1-3, regardless of what the original value in that position was. It should instead be counting 0-3 and skipping the original value. This is why it only produces the correct output when given an all-0 seed. Code follows. Read more... (5 kB) Thanks for the Saturday afternoon diversion!	[reply] [d/l] [select]