CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr
 MAIN INDEX SEARCHPOSTS WHO'S ONLINE LOG IN

Home: Perl Programming Help: Beginner:
check if two strings are permutations

 Print Thread

orange
User

Mar 3, 2017, 12:38 AM

Post #1 of 4 (4242 views)
 check if two strings are permutations Can't Post
I need to compare two strings, say:

\$a="line1\nline2\nline3"
\$b="line3\nline2\nline1"

so that order of lines is ignored.
what would be fast way to do it?
thank you.

Laurent_R
Veteran / Moderator

Mar 3, 2017, 4:36 AM

Post #2 of 4 (4230 views)
 Re: [orange] check if two strings are permutations [In reply to] Can't Post
Usually, the easiest (and very often fastest) way to check whether two pieces of data are permutation of each other (of whether strings are palindromes), is to sort the individual data items of both data inputs and to check whether they compare equal.

BillKSmith
Veteran

Mar 3, 2017, 5:34 AM

Post #3 of 4 (4227 views)
 Re: [orange] check if two strings are permutations [In reply to] Can't Post
It probably is not possible to recognize the fastest way to do anything. It of course is possible to compare alternate approaches. This is what benchmark does. Below, I propose two solutions to your problem and compare them. (Laurent outlined the first while I was preparing this post.)

 Code
use strict;
use warnings;
use Test::Simple tests => 2;
use List::MoreUtils qw(all);

sub compare_via_sort {
my (\$string_a, \$string_b) = @_;
my @arry_a = split /\n/, \$string_a;
my @arry_b = split /\n/, \$string_b;
\$string_a = join "\n", sort @arry_a;
\$string_b = join "\n", sort @arry_b;
return \$string_a eq \$string_b;
}

sub compare_via_hash {
my (\$string_a, \$string_b) = @_;
my %hash_a;
\$hash_a{\$_} = 1 foreach split( /\n/, \$string_a);
return scalar all {defined \$hash_a{\$_}} split( /\n/, \$string_b);
}

our \$string_a="line1\nline2\nline3";
our \$string_b="line3\nline2\nline1";
ok( compare_via_sort(\$string_a, \$string_b), 'sort_compare');
ok( compare_via_hash(\$string_a, \$string_b), 'hash_compare');

use Benchmark qw(cmpthese);

cmpthese 100000, {
sort => my \$ans_sort = 'compare_via_sort(\$string_a, \$string_b)',
hash => my \$ans_hash = 'compare_via_hash(\$string_a, \$string_b)',
}
OUTPUT:
1..2
ok 1 - sort_compare
ok 2 - hash_compare
Rate hash sort
hash 90171/s -- -56%
sort 206186/s 129% --

The results show that both approaches work correctly (at least for this test case). The sort approach is more than twice as fast as the hash approach. Results will be different with real data.
Good Luck,
Bill

orange
User

Mar 3, 2017, 5:44 AM

Post #4 of 4 (4226 views)
 Re: [BillKSmith] check if two strings are permutations [In reply to] Can't Post
great, thank you all very much.

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives