Compare Array Values?

I want to check to see if two arrays contain the same values.
That is, are they the same array but not in the same order.

Example
equal
[1,2,3,4,“abc”] should equal [2,3,1,“abc”,4] and all the other
different
orders that are possible

This should not be equal
[1,2,3] and [1,1,2,3]
[1,2,3,nil] and [nil, nil, nil, 1,2,1,3,2]

At first I thought of
(( array1 | array2 ) - array1).size == 0

but this does not take into account duplicate values and the should not
equals do equal :(. In fact I have not been able work out how to use
any of
the standard array, or Enumerable methods in such a way I can check if
two
arrays contain the same values as well as taking into account
duplicates.

Any pointers?

Cheers
Daniel

I thought I was going to get to contribute, but then I got stuck. I
installed the latest ruby, wrote a quick program that I thought would do
it,
and it didn’t. So I expanded on the program, trying to figure out what
was
going on, and now it’s 20 lines long(mostly puts) and I still don’t
get
something (Beware - the single most basic code ever follows - it was
originally much nicer but then I got to trying to debug)

a = Array.new
a = %w{test test2 test3}
puts a
aSize = a.size
b = Array.new
b = %w{test3 nil test2 test}
bSize = b.size
puts ‘size of b:’ + bSize.to_s
puts b
puts ‘size of a:’ + aSize.to_s
if aSize = bSize
aSorted= a.sort!
bSorted= b.sort!
if aSorted.eql?(bSorted)
puts ‘ssdd’
else
puts ‘same size, different values’
end
else
puts ‘not the same size’
end

ruby array.rb
test
test2
test3
size of b:4
test3
nil
test2
test
size of a:3
same size, different values

What’s wrong with if aSize = bSize? That seems the most intuitive way
to do
it to me… I mean, it’s an integer… why is it going inside the loop
at
all?

On 23/nov/06, at 02:48, Jason M. wrote:

I thought I was going to get to contribute, but then I got stuck. I
installed the latest ruby, wrote a quick program that I thought
would do it,
and it didn’t. So I expanded on the program, trying to figure out
what was
going on, and now it’s 20 lines long(mostly puts) and I still
don’t get
something (Beware - the single most basic code ever follows - it was
originally much nicer but then I got to trying to debug)
[…]
if aSize = bSize
[…]
What’s wrong with if aSize = bSize? That seems the most intuitive
way to do
it to me… I mean, it’s an integer… why is it going inside the
loop at
all?

Just a typo, = instead of == :stuck_out_tongue:

Anyway, you’re relying on the items to respond to <=>. Not every
array should be sortable, I think.
I was thinking of another way, but I’m still working on it…

On Nov 22, 2006, at 8:48 PM, Jason M. wrote:

a = Array.new
a = %w{test test2 test3}
puts a
aSize = a.size
b = Array.new
b = %w{test3 nil test2 test}
bSize = b.size
puts ‘size of b:’ + bSize.to_s
puts b
puts ‘size of a:’ + aSize.to_s
if aSize = bSize

In Ruby = is only used for assignment. For testing use ==.

same size, different values

What’s wrong with if aSize = bSize? That seems the most intuitive
way to do
it to me… I mean, it’s an integer… why is it going inside the
loop at
all?

Regards, Morton

#unsuscribe

2006/11/23, Morton G. [email protected]:

Eek. There goes my street cred.

On 23/nov/06, at 02:04, Daniel N wrote:

I want to check to see if two arrays contain the same values.
That is, are they the same array but not in the same order.

def are_these_arrays_equal?(a1, a2)
return false if a1.size != a2.size
a2 = a2.dup # a2 will be modified, so let’s duplicate it
for i1 in a1
return false unless a2.include? i1
# need to delete just the first occurrence of i1 in a2
# (Array#delete deletes them all)
found = false
a2.delete_if {|i2| found = !found && i1 == i2 }
end
# a2 is now empty, since its size was equal to a1 size
return true
end

This should work with multiple occurrences of the same object,
different objects (so different object_id) that seem to be equal (by
comparing them with ==), nil values (#find() is a bit tricky),
objects that do not respond to <=>.
Did I miss any case?

Anyway I think it’s a bit slow (delete_if goes on even if we deleted
the only one we wanted to, moreover it duplicates a whole array), but
who cares? We’re using ruby, we probably aren’t looking for speed
anyway :stuck_out_tongue:

On Nov 22, 2006, at 8:04 PM, Daniel N wrote:

[1,2,3] and [1,1,2,3]
[1,2,3,nil] and [nil, nil, nil, 1,2,1,3,2]

In general, if the arrays can contain arbitrary elements, this is a
difficult problem. If the elements themselves can be arrays, you will
want to start by duplicating the two arrays and flattening the
duplicates. If the duplicates are not the same size, you’re done. If
they are the same size, you will need to define a notion of canonical
order (basically a sort order that is applicable to all elements) and
transform both arrays into canonical order – this can be the hard
part. Then you can make an element by element comparison.

Regards, Morton

Hi –

On Thu, 23 Nov 2006, Jason M. wrote:

I thought I was going to get to contribute, but then I got stuck. I
installed the latest ruby, wrote a quick program that I thought would do it,
and it didn’t. So I expanded on the program, trying to figure out what was
going on, and now it’s 20 lines long(mostly puts) and I still don’t get
something (Beware - the single most basic code ever follows - it was
originally much nicer but then I got to trying to debug)

There are a few cobwebs you can clear :slight_smile:

a = Array.new
a = %w{test test2 test3}

You’re using the identifier ‘a’ twice. The first use is discarded.
You might as well do:

a = 1000
a = %w{ test test2 test3 }

The second assignment clobbers the first, with respect to the
variable.

puts a
aSize = a.size
b = Array.new
b = %w{test3 nil test2 test}

Do you really want the string “nil” there, as opposed to the object nil?

bSize = b.size
puts ‘size of b:’ + bSize.to_s
puts b
puts ‘size of a:’ + aSize.to_s
if aSize = bSize

You mean:

if aSize == bSize

aSorted= a.sort!
bSorted= b.sort!

This is OK if everything in both arrays is sortable, but they may not
be:

[1,2,nil,3].sort # => ArgumentError

You can’t compare nil to an integer, nor a string to an integer, etc.,
so an array with mixed objects like that can’t sort.

Here’s another way to go about it. I imagine someone will come along
with a slicker and/or more efficient implementation of the method, but
for what it’s worth, here’s mine:

require ‘test/unit’

module EnumerableAddons

def count(element)
find_all {|e| e == element }.size
end

def equal_to(other)
all? {|e| other.count(e) == count(e) }
end
end

class ArrayComparisonTest < Test::Unit::TestCase

def setup
@a = [1,2,3,4,nil,“hi”].extend(EnumerableAddons)
@b = [2,3,nil,4,“hi”,1].extend(EnumerableAddons)
end

def test_same
assert(@a.equal_to(@b))
end

def test_duplicate
@a << 1
assert(!@a.equal_to(@b))
end

def test_extra
@a << 5
assert(!@a.equal_to(@b))
end

def test_subset_of_same_size
@a.pop
@a << 1
assert(!@a.equal_to(@b))
end

end

There’s an noteworthy lesson about testing here, by the way. My first
implementation of equal_to was:

def equal_to(other)
end

Interestingly, some of my tests passed – because the method returned
nil, and I was asserting (the truth of (not the method return value)).
It’s a useful reminder of the possibility of things working by
coincidence sometimes.

David

Hi –

On Thu, 23 Nov 2006, Gabriele M. wrote:

return false unless a2.include? i1

objects (so different object_id) that seem to be equal (by comparing them
with ==), nil values (#find() is a bit tricky), objects that do not respond
to <=>.
Did I miss any case?

It passes all of my tests (see my other email).

Anyway I think it’s a bit slow (delete_if goes on even if we deleted the only
one we wanted to, moreover it duplicates a whole array), but who cares? We’re
using ruby, we probably aren’t looking for speed anyway :stuck_out_tongue:

Well… we don’t complain when things are faster :slight_smile: Doing a few
benchmarks it appears that yours is faster than mine. I added a
“return false if [sizes differ]”, and that helped with those runs.

David

Well, I’m new to Ruby, but it was an interesting question so I gave it
a stab. My first idea was

a.sort == b.sort

which works if all the elements of an array of of the same class. But
if you mix objects of different class (like you example with Fixnums
and a String), sort() craps out on it. You can pass a block to sort,
but I couldn’t think of a good way to use that to our advantage. So I
resorted to more of a brute force method:

def same_elems?(array1, array2)
return false unless array1.length == array2.length

tmp = array2.clone
array1.each do |item|
if i = tmp.index(item) then tmp.delete_at(i) end
end
return tmp.empty?
end

As far as I can tell it meets all of your criteria.

Darshan

Hi –

On Thu, 23 Nov 2006, Morton G. wrote:

This should not be equal
comparison.
I’m not sure about the flattening. If you have:

[1,2,[3,4],5]

and

[1,[2,3],4,5]

as I understand it, the comparison should fail, because the arrays
contain different elements, not the same elements in possibly
different order. I guess we’d need a ruling from Daniel.

David

Wow… I go out to lunch and the response is great.

A test case is a great idea David. I’ve made some adjustments to your
setup
to meet my requirements. valid and invalid are in comparison to the
@std
array.

I wish I could try these out but I’ll have to wait until I get home to
have
a good go at it.

On 11/23/06, [email protected] [email protected] wrote:

require ‘test/unit’

class ArrayComparisonTest < Test::Unit::TestCase

def setup

     @std = [1,2,3,4,5,"abc",nil]
     @valid_arrays =[ [ 2,3,1,4,nil,5,"abc"],

[2,1,nil,“abc”,5,3,4],[1,3,2,4,[“abc”],5,nil]]

     @invalid_arrays = [
                                 [nil,nil,nil],
                                 [nil,nil,nil,nil,nil,nil,nil],
                                 [1,2,3,1,2,3,1],
                                 ["abc","abc",1,2,3,4,5],
                                 ["abc",1,2,3,4,5,1],
                                 [["abc",1],1,2,3,4,5,nil]
                                ]
   end

On 11/22/06, Daniel N [email protected] wrote:

[1,2,3,nil] and [nil, nil, nil, 1,2,1,3,2]

At first I thought of
(( array1 | array2 ) - array1).size == 0

but this does not take into account duplicate values and the should not
equals do equal :(. In fact I have not been able work out how to use any of
the standard array, or Enumerable methods in such a way I can check if two
arrays contain the same values as well as taking into account duplicates.

Any pointers?

What’s wrong with:

irb(main):002:0> require ‘set’
=> true
irb(main):003:0> t1 = [1,2,3,4,“abc”]
=> [1, 2, 3, 4, “abc”]
irb(main):004:0> t2 = [2,3,1,“abc”,4]
=> [2, 3, 1, “abc”, 4]
irb(main):005:0> s1 = Set.new(t1)
=> #<Set: {“abc”, 1, 2, 3, 4}>
irb(main):006:0> s2 = Set.new(t2)
=> #<Set: {“abc”, 1, 2, 3, 4}>
irb(main):007:0> s1 == s2
=> true
irb(main):008:0> s1.subset?(s2)
=> true
irb(main):009:0> s2.subset?(s1)
=> true

Cheers
Daniel


Stuart Yarus

On 11/23/06, Gabriele M. [email protected] wrote:

 for i1 in a1

This should work with multiple occurrences of the same object,
different objects (so different object_id) that seem to be equal (by
comparing them with ==), nil values (#find() is a bit tricky),
objects that do not respond to <=>.
Did I miss any case?

I’ve made a list of the cases so far that I can think of, in a response
to
Davids post. The elements could be of arbitrary type.

Anyway I think it’s a bit slow (delete_if goes on even if we deleted

the only one we wanted to, moreover it duplicates a whole array), but
who cares? We’re using ruby, we probably aren’t looking for speed
anyway :stuck_out_tongue:

The case that I want to use it for is as a test helper so speed is not
critical. I want to make sure that I don’t have duplicate attributes in
an
association in rails that is not a straight forward use of
validates_uniquness_of

Thanx for your help… I’ll give this one a go when I get to my
computer.

On 11/23/06, Darshan.Ishaya [email protected] wrote:

resorted to more of a brute force method:

As far as I can tell it meets all of your criteria.

Darshan

Hi Darshan,

Thanx for you response. I looks like it should do the trick. Thanx

On 11/23/06, stuart yarus [email protected] wrote:

irb(main):005:0> s1 = Set.new(t1)
=> #<Set: {“abc”, 1, 2, 3, 4}>
irb(main):006:0> s2 = Set.new(t2)
=> #<Set: {“abc”, 1, 2, 3, 4}>
irb(main):007:0> s1 == s2
=> true
irb(main):008:0> s1.subset?(s2)
=> true
irb(main):009:0> s2.subset?(s1)
=> true

This would remove duplicates prior to the comparison. I want to do the
comparison on the raw arrays since if there is duplicates in one and not
the
other then they should not be equal.

The Coolest Way:

def same_elems?(array1, array2)
return false unless array1.length == array2.length

compare = Proc.new do |x,y|
if (x.class == y.class)
x <=> y
else
x.class.to_s <=> y.class.to_s
end
end

return array1.sort(&compare) == array2.sort(&compare)
end

Ruby sure is fun. Like I said, I’m new to Ruby, so I’m still getting a
kick out of all this stuff. I’m pretty sure this works (i.e, meets all
of your criteria), and man do I think it’s cool that you can do this.
Remember I said you could pass a block to sort()? Well, I just did
what I wanted (I’m not used to being ABLE to do what I want, Ruby seems
to make it way easier to just tell it to do what you want it to.)

I guess it’ll work for any two arrays filled with objects of any
classes that have <=> defined. That should be most, I think. I just
tell sort() to compare with <=> if the objects to be compared are of
the same class, and if not, sort by putting the one whose class name
comes first alphabetically (converting their class names to Strings and
comparing those with <=>). So you get a sorted array with, e.g. Arrays
first, then Fixnums, then Stings, then Symbols, or whatever, but
classes in order, and in order within the classes.

It’s conceptually simple, but I have no idea how it compares in speed
to the other ways. Can anyone give me a tip on a good way to
benchmark?

Darshan

On 11/23/06, Darshan.Ishaya [email protected] wrote:

  x.class.to_s <=> y.class.to_s
end

end

return array1.sort(&compare) == array2.sort(&compare)
end

That is cool.

It’s conceptually simple, but I have no idea how it compares in speed

to the other ways. Can anyone give me a tip on a good way to
benchmark?

There is a benchmarking class built into core

the docs are at
http://www.ruby-doc.org/core/classes/Benchmark.html

There are a couple of examples there of its usage too.

thanx for your help with this one

On 23/nov/06, at 03:14, Gabriele M. wrote:

# a2 is now empty, since its size was equal to a1 size
return true

end

This should work with multiple occurrences of the same object,
different objects (so different object_id) that seem to be equal
(by comparing them with ==), nil values (#find() is a bit tricky),
objects that do not respond to <=>.
Did I miss any case?

I’m replying to myself.

Morton smartly pointed out that elements can be arrays themselves.
So, should we treat them as any other kind of object and compare them
with ==?
I guess we should want to recursively apply our equality concept
given by the OP.
So I modified my version:

def are_these_arrays_equal?(a1, a2)
return false unless a1.kind_of? Array and a2.kind_of? Array
return false if a1.size != a2.size
a2 = a2.dup # a2 will be modified, so let’s duplicate it
for i1 in a1
return false unless a2.any? do |i2|
if i1.kind_of? Array
are_these_arrays_equal?(i1, i2)
else
i1 == i2
end
end
# need to delete just the first occurrence of i1 in a2
# (Array#delete deletes them all)
found = false
a2.delete_if do |i2|
break if found # breaks if already deleted
found = !found && if i1.kind_of? Array
are_these_arrays_equal?(i1, i2)
else
i1 == i2
end
end
end
# a2 is now empty, since its size was equal to a1 size
return true
end

Of course this would be much simpler if we were redefining Array#==
with this algorythm (there would be no need to check #kind_of?) but I
really DON’T want to know what could happen by redefining Array#==,
since every library could rely on it :stuck_out_tongue:
(Actually, it might be funny to find out)