comparing two arrays to find out if they are permuation of each other

[dipti1]

Hi there,

Is there any way of comparing two arrays in perl to find out if they are permuation of each other ?

For example,
if @a = {1,2,3};
@b = {3,1,2};

they the result should be true.

Thank you in advance,
priya

 

[TrojanWarBlade]

Maybe this might be a start:

#!/usr/bin/perl
use warnings;
use strict;

my @a = (1,2,3);
my @b = (3,1,2);
my $result = 'true';
{
    my @c = sort @a;
    my @d = sort @b;
    # Check for same length
    $result = 'false', last if($#a != $#b);
    for(my $i=0; $i<=$#a; $i++) {
        # WARNING: Numeric test below.  Assuming all numeric entries.
        $result = 'false', last unless($c[$i] == $d[$i]);
    }
}
# Here result is 'true' if they match or 'false' otherwise
print $result, "\n";

Trojan.

 

[dipti1]

Thanks but this does not work.

I need to check if some permuation of @b is equal to @a.

Is there any in built subroutine or function in perl that will check this ?

Thank you,

priya

 

[cdlvj]

http://search.cpan.org/~allenday/Math-Combinatorics-0.08/lib/Math/Combinatorics.pm

May work for you.

 

[KevinADC]

maybe:

http://search.cpan.org/~davecross/Array-Compare-1.13/lib/Array/Compare.pm

 

[TrojanWarBlade]

What does "Thanks but this does not work" mean?
Why doesn't it work?
What does it do or not do that you need it to do?
What do you mean by "I need to check if some permuation of @b is equal to @a"?
I assumed that you were looking to see if the two arrays contained the same elements irrespective of sequence.


Trojan.

 

[PaulTEG]

That's what I thought too, and it looks like the code posted by TWB works for such an assumption. I have a feeling there's something the OP is not telling us....

--Paul


Paul
------------------------------------
Spend an hour a week on CPAN, helps cure all known programming ailments ;-)

 

[dipti1]

Oh I am sorry that I did not make the problem more clear.

Suppose I have an array a = {2,1,3}
also suppose I have an array b = {1,2,3}.

So now, I want to check if some ordering of array b matches with array a.

The sequence of elements of array b can be:
{1,2,3},{2,1,3},{3,1,2},{3,2,1}...and so on. So from here, the second array-{2,1,3} matches with array a={2,1,3}.

So my question was that is there any way to find that out.

Thank you!

 

[KevinADC]

maybe:

use List::Permutor;
my @array = (2,1,3);
my @array1 = (1,2,3);
my $perm = new List::Permutor @array;
while (my @set = $perm->next) {
   if ("@array1" eq "@set") {
      print "\@array1 is a permuation of \@array: @array\n";
      last;
   }
}

 

[TonyGroves]

How about:
[tt]
$same=(join' ',sort@a)eq(join' ',sort@b);
[/tt]

 

[KevinADC]

I think the example arrays are very simplified. I assume the real arrays are probably longer and of mixed data, so a simple sort may not work.

 

[TonyGroves]

The sort order doesn't matter, as long as the same sort order is applied to both arrays. However, the join character would need to be unique, guaranteed not to be present in either array.

 

[TrojanWarBlade]

The point here is that if you sort both arrays you can see if the sorted versions are the same. The only way that can be the case is if there is a permutation that matches.
I think TonyGroves idea is absolutely superb, if answers your question in one simple statement that you could bury in an "if" test.


Trojan.

 

[KevinADC]

The sort order doesn't matter, as long as the same sort order is applied to both arrays. However, the join character would need to be unique, guaranteed not to be present in either array.

Yes, you are absolutely correct. It is essentially what the array::compare module does internally:

Internally the comparator compares the two arrays by using join to turn both arrays into strings and comparing the strings using eq. In the joined strings, the elements of the original arrays are separated with the ^G character. This can cause problems if your array data contains ^G characters as it is possible that two different arrays can be converted to the same string.

 

[ishnid]

Sorting and then comparing is likely to be far more efficient than finding all the possible permutations of an array and comparing each one with the first array in question.