Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Finding String's Neighbors By Up To 2 Differing Positions

by neversaint (Deacon)
on Mar 27, 2009 at 13:16 UTC ( #753648=perlquestion: print w/replies, xml ) Need Help??

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
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"; } } }


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

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; }

    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

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.

    Cheers - L~R

Re: Finding String's Neighbors By Up To 2 Differing Positions
by dsheroh (Prior) 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.

    Thanks for the Saturday afternoon diversion!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://753648]
Approved by moritz
Front-paged by monkfan
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (3)
As of 2020-02-22 10:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What numbers are you going to focus on primarily in 2020?










    Results (99 votes). Check out past polls.

    Notices?