CODEWITHSUNDEEP
javaalgorithmmath
Mikey
Mikey

Reputation: 21

Finding pairs of duplicates in a Java ArrayList

I'm looking to find the number of duplicate pairs in a Java ArrayList.

I can work it out on paper but I don't know if there is some form of mathematical formula for working this out easily as I'm trying to avoid nested for loops in my code.

An example using the data set [2,2,3,2,2]: 0:1, 0:3, 0:4, 1:3, 1:4, 3:4. So the answer is six duplicate pairs?

Upvotes: 2

Views: 1912

Answers (4)

Kaleb Brasee
Kaleb Brasee

Reputation: 51945

If you want to avoid nested loops (at the expense of having 2 loops), you could:

  1. for each number in the list, find how many times each number is repeated (maybe use a Map with key = number, value = times that number occurred in the List)
  2. for each number in the map, calculate the number of possible combinations based on the times that it occurred (0 or 1 times = no duplicate pairs, 2 or more = n!/(2*(n-2)!) = (n*(n-1))/2 duplicate pairs)
  3. sum all the possible combinations

Doing a sort like ElKamina suggests would allow for some optimization on this method.

Upvotes: 2

Louis Wasserman
Louis Wasserman

Reputation: 198103

Using Guava, if your elements were Strings:

Multiset<String> multiset = HashMultiset.create(list);
int pairs = 0;
for(Multiset.Entry<String> entry : multiset.entrySet()) {
  pairs += IntMath.binomial(entry.getCount(), 2);
}
return pairs;

That uses Guava's Multiset and math utilities.

Upvotes: 0

Francisco Paulo
Francisco Paulo

Reputation: 6322

You just need to count how many times each number appears (I would go with a map here) and calculate 2-combinations ( http://en.wikipedia.org/wiki/Combination ) of that count for each number with a count > 1.

So basically you need a method to calculate n!/k!(n-k)! with k being 2 and n being the count.

Taking your example [2,2,3,2,2], the number 2 appears 4 times, so the math would go:

4!/2!(4-2)! = 24/4 = 6 --> 6 pairs

If you don't want to implement the factorial function, you can use the ArithmeticUtils from Apache Commons, they already have the factorial implemented.

Upvotes: 4

ElKamina
ElKamina

Reputation: 7807

Sort the numbers first. Later, if there k copies of a given number, there will be k*(k-1)/2 pairs from that number. Now sum it over all the numbers.

Upvotes: 0

Related Questions