How to get non-unique elements from an array?


S

Sam Kong

Hello!

I need to get non-unique elements from an array.
The best I came up with was using a hash as a counter for each unique
elements.

a = [0,1,2,3,4,5,2,3]

#What I want to get is [2,3] as 2,3 are non-unique elements.

h = {}
a.each do |i|
if h
h += 1
else
h = 1
end
end

u = []
h.each do |k, v|
if v > 1
u << k
end
end

#now u == [2,3]

This works fine.
But I think there's a better way.
How do you handle such a case?

Thanks in advance.

Sam
 
Ad

Advertisements

P

Paolo Capriotti

Hello!

I need to get non-unique elements from an array.
The best I came up with was using a hash as a counter for each unique
elements.

You don't need the exact number of repetitions. Try this:
a =3D [0,1,2,3,4,5,2,3]
h =3D {}
u =3D a.inject([]) {|res, x| h[x] ? res + [x] : h[x] =3D res}

Paolo
 
J

James Edward Gray II

Hello!

I need to get non-unique elements from an array.
The best I came up with was using a hash as a counter for each unique
elements.

a = [0,1,2,3,4,5,2,3]

#What I want to get is [2,3] as 2,3 are non-unique elements.

Here's what I thought of:
a = [0,1,2,3,4,5,2,3] => [0, 1, 2, 3, 4, 5, 2, 3]
seen = Hash.new(0) => {}
a.select { |e| (seen[e] += 1) > 1 }.uniq
=> [2, 3]

Hope that helps.

James Edward Gray II
 
S

Simon Strandgaard

I need to get non-unique elements from an array.
The best I came up with was using a hash as a counter for each unique
elements.

How about?

ary =3D [1, 1, 2, 3, 3, 4, 2, 5, 7]
#=3D> [1, 1, 2, 3, 3, 4, 2, 5, 7]
uary =3D ary.uniq; ary.map.delete_if{|i| x=3Duary.member?(i); uary.delete(i=
); x}
#=3D> [1, 3, 2]
 
S

Sam Kong

You don't need the exact number of repetitions. Try this:
a = [0,1,2,3,4,5,2,3]
h = {}
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}

Thank you for the insight.

However, your code doesn't work if an element repeats more than twice.

a = [0,1,2,3,4,5,2,3,2] #there are three 2's.
Your code's result is [2, 3, 2] instead of [2, 3]
It should be modified like
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}.uniq

Other than that, I like your way.
Thank you again.

Sam
 
R

Robert Klemme

Sam Kong said:
You don't need the exact number of repetitions. Try this:
a = [0,1,2,3,4,5,2,3]
h = {}
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}

Thank you for the insight.

However, your code doesn't work if an element repeats more than twice.

a = [0,1,2,3,4,5,2,3,2] #there are three 2's.
Your code's result is [2, 3, 2] instead of [2, 3]
It should be modified like
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}.uniq

Other than that, I like your way.
Thank you again.

Sam
 
Ad

Advertisements

R

Robert Klemme

Sam Kong said:
You don't need the exact number of repetitions. Try this:
a = [0,1,2,3,4,5,2,3]
h = {}
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}

Thank you for the insight.

However, your code doesn't work if an element repeats more than twice.

a = [0,1,2,3,4,5,2,3,2] #there are three 2's.
Your code's result is [2, 3, 2] instead of [2, 3]
It should be modified like
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}.uniq

Other than that, I like your way.
Thank you again.

Sam
a = [0,1,2,3,4,5,2,3] => [0, 1, 2, 3, 4, 5, 2, 3]
a.inject(Hash.new(0)) {|h,e| h[e]+=1;h}.select {|k,v|v>1}.map {|a,b|a}
=> [2, 3]

Quite complicated...

robert
 
S

Simon Kröger

Robert said:
Sam Kong said:
You don't need the exact number of repetitions. Try this:
a = [0,1,2,3,4,5,2,3]
h = {}
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}


Thank you for the insight.

However, your code doesn't work if an element repeats more than twice.

a = [0,1,2,3,4,5,2,3,2] #there are three 2's.
Your code's result is [2, 3, 2] instead of [2, 3]
It should be modified like
u = a.inject([]) {|res, x| h[x] ? res + [x] : h[x] = res}.uniq

Other than that, I like your way.
Thank you again.

Sam
a = [0,1,2,3,4,5,2,3]

=> [0, 1, 2, 3, 4, 5, 2, 3]
a.inject(Hash.new(0)) {|h,e| h[e]+=1;h}.select {|k,v|v>1}.map {|a,b|a}

=> [2, 3]

Quite complicated...

Yeah,

some thoughts of mine:

---------------------------------------------------------------------
require 'enumerator'

a = [0,1,2,3,4,3,5,2,3]

p a.sort.to_enum:)each_cons, 2).select{|i, j|i==j}.flatten.uniq

p a.select{|x|a.index(x) != a.rindex(x)}.uniq

p a.dup.reject{|x|a.delete(x)}.uniq
---------------------------------------------------------------------

all have downsides (performance wise and the last one is destructive)

cheers

Simon
 
R

Robert Klemme

Hello!

How about this ?
(0...a.length-1).select{|i| a==a[i+1]}.map{|i|a}.uniq


a needs to be sorted for this to work. As far as I remember that was not a
guaranteed precondition so you would have to add that here.

IMHO most efficient variants are still those that use a hash for element
counting.

Kind regards

robert
 
A

Ara.T.Howard

Hello!

How about this ?
(0...a.length-1).select{|i| a==a[i+1]}.map{|i|a}.uniq


a needs to be sorted for this to work. As far as I remember that was not a
guaranteed precondition so you would have to add that here.

IMHO most efficient variants are still those that use a hash for element
counting.


and you needed even count i think:

harp:~ > cat a.rb
class Array
def dups
h, d = {}, []; each{|e| h[e] ? (d << h.delete(e)) : (h[e] = e) }; d
end
end

a = 0, 1, 2, 3, 4, 5, 2, 3, 2

p a.dups


harp:~ > ruby a.rb
[2, 3]

regards.

-a
--
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| anything that contradicts experience and logic should be abandoned.
| -- h.h. the 14th dalai lama
===============================================================================
 
Ad

Advertisements

D

David A. Black

Hi --

Hello!

I need to get non-unique elements from an array.
The best I came up with was using a hash as a counter for each unique
elements.

a = [0,1,2,3,4,5,2,3]

#What I want to get is [2,3] as 2,3 are non-unique elements.

One probably slow but kind of cool way is:

a.uniq.find_all {|x| a.find_all {|y| y == x }.size > 1 }


David
 
R

Robert Klemme

Ara.T.Howard said:
Hello!

How about this ?
(0...a.length-1).select{|i| a==a[i+1]}.map{|i|a}.uniq


a needs to be sorted for this to work. As far as I remember that
was not a guaranteed precondition so you would have to add that here.

IMHO most efficient variants are still those that use a hash for
element counting.


and you needed even count i think:

harp:~ > cat a.rb
class Array
def dups
h, d = {}, []; each{|e| h[e] ? (d << h.delete(e)) : (h[e] = e)
}; d end
end

a = 0, 1, 2, 3, 4, 5, 2, 3, 2

p a.dups


harp:~ > ruby a.rb
[2, 3]


Did you mean to provide this as an example that you actually need to count?
Because that's what it is:

?> a = 0, 1, 2, 3, 4, 5, 2, 3, 2, 2
=> [0, 1, 2, 3, 4, 5, 2, 3, 2, 2]?> p a.dups
[2, 3, 2]
=> nil
Here's another alternative with limited counting:
a = 0, 1, 2, 3, 4, 5, 2, 3, 2, 2 => [0, 1, 2, 3, 4, 5, 2, 3, 2, 2]
a.inject({}) do |h,i| ?> case h
when nil
h = 1
when 1
h = 2
when 2
# ok

?> else
?> raise "Error"
end
h
end.inject([]) {|ar,(k,v)| ar << k if v == 2; ar}
=> [2, 3]

I doubt though that performance is better than that with counting.

Kind regards

robert
 
A

Ara.T.Howard

Did you mean to provide this as an example that you actually need to count?
Because that's what it is:

no - i meant you have to count - merely note that a element has been seen and,
if so, add it to the list. i notice now my example has a bug in that an
element occuring 4 times is added twice. it's easy fix though. i suppose you
could call that counting - but's it's really only 0 or 1, seen or seen again.

cheers.

-a
--
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| anything that contradicts experience and logic should be abandoned.
| -- h.h. the 14th dalai lama
===============================================================================
 
R

Robert Klemme

Ara.T.Howard said:
no - i meant you have to count - merely note that a element has been
seen and, if so, add it to the list. i notice now my example has a
bug in that an element occuring 4 times is added twice.

More precisely speaking: for every even number it's added half that many
times because you insert into the Hash and delete and insert and... :)
it's easy
fix though. i suppose you could call that counting - but's it's
really only 0 or 1, seen or seen again.

Yep, like I tried to show with my other example which really knows only
three states: not in hash, once in hash, more than once in hash. That's
probably the minimalistic set of states that will suffice to solve the
problem.

Kind regards

robert
 
L

Lyndon Samson

------=_Part_16516_23987217.1129513116683
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Not very elegant, but a different approach...

bn =3D bn2 =3D 0
a.each {|el|(bn2 |=3D (1<<el) if (bn & ( 1<<el) ) !=3D 0) | bn |=3D (1<<el)=
}
0.upto(a.length) { |bitNdx| puts bitNdx if (bn2 & ( 1<<bitNdx )) !=3D 0 }

------=_Part_16516_23987217.1129513116683--
 
Ad

Advertisements

L

Lyndon Samson

------=_Part_16588_17409819.1129513472547
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Funny, doesnt work when an item in the array > 10...

Plus, reading the documentation ( doh! ) I can access a Bignum bit with []
 
E

Explosiv0SX

You could just sort the array, then iterate. If the previous
iteration value is equal to the current, you have a non-unique. This
would work with string or numeric data types.

Rick

Funny, doesnt work when an item in the array > 10...

Plus, reading the documentation ( doh! ) I can access a Bignum bit
with []


Not very elegant, but a different approach...

bn = bn2 = 0
a.each {|el|(bn2 |= (1<<el) if (bn & ( 1<<el) ) != 0) | bn |=
(1<<el) }
0.upto(a.length) { |bitNdx| puts bitNdx if (bn2 & ( 1<<bitNdx )) !
= 0 }
 
J

Joe Van Dyk

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


You could just sort the array, then iterate. If the previous
iteration value is equal to the current, you have a non-unique.
This would work with string or numeric data types.

Rick

On Oct 16, 2005, at 9:44 PM, Lyndon Samson wrote:

Or, probably not efficient, but:

irb(main):031:0> a
=> [1, 2, 3, 4, 5, 5, 3]

irb(main):032:0> a.find_all { |x| a.find_all { |y| y == x }.size >
1 }.uniq
=> [3, 5]
Funny, doesnt work when an item in the array > 10...

Plus, reading the documentation ( doh! ) I can access a Bignum bit
with []


Not very elegant, but a different approach...

bn = bn2 = 0
a.each {|el|(bn2 |= (1<<el) if (bn & ( 1<<el) ) != 0) | bn |=
(1<<el) }
0.upto(a.length) { |bitNdx| puts bitNdx if (bn2 & ( 1<<bitNdx )) !
= 0 }

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iD8DBQFDUyjpsWh6/7z1gt4RAs02AJ4r8HY5/CgXDjfP50hPBaEzpFY+jQCeI8he
tA0HUlGZk4eshlTS+xxGmag=
=T67U
-----END PGP SIGNATURE-----
 
Ad

Advertisements

Z

zdennis

I don't' think I've seen this solution yet, so here's my stab:

irb(main):013:0> a = [1,2,5,4,3,5,3]
=> [1, 2, 5, 4, 3, 5, 3]

irb(main):017:0> t=[]; a.delete_if{ |e| r=(not t.include? e); t.push(e); r }
=> [5, 3]

Zach
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top