Re: Algorithm to find pairs in array [can not order]

From:

Patricia Shanahan <pats@acm.org>

Newsgroups:

comp.lang.java.programmer

Date:

Fri, 17 Nov 2006 13:56:07 GMT

Message-ID:

<Xbj7h.8716$ig4.1331@newsread2.news.pas.earthlink.net>

obaqueiro@gmail.com wrote:

Hello, so I am trying to make a better (with less complexity,
prefferably without a nested loop) to find something like pairs of
items in an ArrayList:

So far I've got this:

// shuffle Option offers
Collections.shuffle(offeredOptions);
for (int i=0;i<offeredOptions.size()-1;i++)
{
    Offer of1 = offeredOptions.get(i);
    // look for a matching option offer in the list
      for (int j=1;j<offeredOptions.size();j++)
               {
        Offer of2 = offeredOptions.get(j);
/* we are looking for 2 offers for the same Option contract with
opposite
         * offer types (write and hold)
        */
        if (of1.getOption() == of1.getOption() &&
            (of1.type == OfferType.hold && of2.type == OfferType.write) ||
            (of1.type == OfferType.write && of2.type == OfferType.hold))
            {
                offeredOptions.remove(i);

offeredOptions.remove(j);
                                                 // do something else
...
                                                 // ...
                                                  break; // get to the
i loop

            }
    }
}

I know it is not optimal, but basically I need to match 2 items from
the array (which is randomized), and then remove them.
I am sure there must be a more efficient way to do this but I cant
remember the proper algorithm...

I know it is not a *proper* Java question but didn't knew which group
to address

thanks anyway!

There is a quick halving of the work. The inner loop does not need to
begin from index 1. It can start from i+1, because any match between a
pair either of which has an index value less than i would have been
found on a previous outer loop iteration.

If you rely on direct comparison, using the unordered array, the work is
going to be O(n*n).

What is the type of a getOption() result? Can there be more than two
offers with the same contract?

Depending on those answers, there may be much more efficient solutions
for large n in which the data gets copied to a HashSet or HashMap during
the search.

Patricia