aspose file tools*
The moose likes Beginning Java and the fly likes How to Retrieve all Equal Objects from a List ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "How to Retrieve all Equal Objects from a List ?" Watch "How to Retrieve all Equal Objects from a List ?" New topic
Author

How to Retrieve all Equal Objects from a List ?

Jose Campana
Ranch Hand

Joined: May 28, 2007
Posts: 339
Hello there,

I was wondering if there's an easier way to do what i'm trying to code...

If I have an Ordered list, whose Contained objects correctly implement the Comparable interface's compareTo method, in such a way that after sorting (by using the Collections.sort() method) you get
an ordered list like the one below:

{ "AA", "AA", "AA", "CC", "CC", "DD" }

Is there a way to easily create sub-lists for each of the objects that are common between one-another ?

in other words: For the List above, I should get 3 sub-Lists:

{"AA", "AA", "AA"}
{"CC", "CC"}
{"DD"}

Is there an easy way to do this by using the Collections framework ?

I've just spent more than the adequate time trying to do this, and probably there's an easier way,

I hope to read your comments soon to see If I can fix my algorithm.

How would you guys do it?

Best Regards,

Jose
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
Jose Campana wrote:How would you guys do it?


If the list is ordered you only need to iterate through it once to split it up in sublists like that.

It's because all equal items appear in groups. When you iterate the list and find a new item you create a sublist and fill it with items as long as they're equal. Then you create a new sublist filling it, etcetera.
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
There's another algorithm which doesn't require the list to be sorted.

This solution uses a HashMap. The HashMap keys are the list items and the HashMap values are the sublists.

You scan the list once and consider each item. If an item is not in the HashMap you enter it together with a sublist containing the item. If the item is already in the HashMap you just add it to the corresponding sublist. Afterwards the HashMap values are the sublists.
Siva Masilamani
Ranch Hand

Joined: Sep 19, 2008
Posts: 385
try this


SCJP 6,SCWCD 5,SCBCD 5

Failure is not an option.
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
Siva Masilamani wrote:try this


Note that although this algorith may work it's unnecessarily complex. It's a quadratic solution to a linear problem.

Siva Masilamani
Ranch Hand

Joined: Sep 19, 2008
Posts: 385
why?

Don;t take it offensively but could you tell me why it is complex?

Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
Siva Masilamani wrote:why?

Don;t take it offensively but could you tell me why it is complex?



Your solution is complex in the algorithmic sense. It's O(N*N) when it only needs to be O(N) (where N is the number of items in the list).

In princple it's because for each unique item in the list you scan the list from the beginning.
Jose Campana
Ranch Hand

Joined: May 28, 2007
Posts: 339
Embla Tingeling wrote:There's another algorithm which doesn't require the list to be sorted.

This solution uses a HashMap. The HashMap keys are the list items and the HashMap values are the sublists.

You scan the list once and consider each item. If an item is not in the HashMap you enter it together with a sublist containing the item. If the item is already in the HashMap you just add it to the corresponding sublist. Afterwards the HashMap values are the sublists.


Good day !

This solution you have just mentioned, which uses a HashMap sounds totally appealing to me, mostly because I was considering HashMap myself.
Embla could you clarify with a little example how would you implement this solution. I really want to see it, an image(in this case some code) is worth a thousand words.

I'd love to see it, and hope it's not much of a trouble.

Sincerely, Jose.
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
Jose Campana wrote:I'd love to see it, and hope it's not much of a trouble.


It's a standard solution to all sorts of counting problems. It goes like this in this particular case,


Jose Campana
Ranch Hand

Joined: May 28, 2007
Posts: 339
Embla,

Let me just say this,

It's Magnificent. Thanks for the contribution. Wow... amazing.

It's good to know that there's always room for learning, I'm glad for it !

I can't help but asking, Where did you learn this technique ?

I'm so curious,

Jose
Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
Jose Campana wrote:I can't help but asking, Where did you learn this technique ?


I don't remember anymore but it's a standard algorithm really.

The most common use is for frequency counting I think. For example when you have a textfile and need to count how many times each word occurs in the text. In that case the HashMap would hold a counter for each word.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How to Retrieve all Equal Objects from a List ?