Поиск пар дубликатов в Java ArrayList

Question

Я ищу, чтобы найти количество дубликатов пар в Java ArrayList.

Я могу обработать его на бумаге, но я не знаю, есть ли какая-то форму математической формулы для этого легко, поскольку я пытаюсь избежать вложенных циклов в моем коде.

Пример использования набора данных [2,2,3,2,2]: 0: 1, 0: 3, 0: 4, 1: 3, 1: 4, 3: 4. Итак, ответ состоит из шести повторяющихся пар?

Answer 1

Сортировка номеров в первую очередь. Позже, если там k копий данного номера, из этого числа будет k*(k-1)/2 пар. Теперь суммируем его по всем числам.

Answer 2

Вам просто нужно подсчитать, сколько раз каждое число появляется (я бы с картой здесь) и вычислить 2-комбинации (http://en.wikipedia.org/wiki/Combination) этого графа для каждого числа с числом> 1.

Так в основном вам нужен метод для вычисления n!/k!(n-k)! с k, являющимся 2, и n является счетчиком.

Берем пример [2,2,3,2,2], число 2 появляется в 4 раза, так что математика будет идти:

4/2 (4-2)!! = 24/4 = 6 -> 6 пар

Если вы не хотите использовать факториальную функцию, вы можете использовать ArithmeticUtils из Apache Commons, у них уже есть factorial implemented.

Answer 3

Если вы хотите, чтобы избежать вложенных циклов (за счет наличия 2 петли), вы можете:

1. для каждого номера в списке, найти, сколько раз каждое число повторяется (возможно использовать карту с ключом = число, значение = число, которое произошло в списке)
2. для каждого номера на карте, рассчитать количество возможных комбинаций в зависимости от времени, которое оно произошло (0 или 1 раз = нет повторяющихся пар, 2 или более = n!/(2 * (n-2)!) = (n * (n-1))/2 дублирующие пары)
3. суммировать все возможные комбинации

Выполнение подобного рода предложения, предложенного ElKamina, позволило бы оптимизировать этот метод.

Answer 4

Использование Guava, если ваши элементы были String s:

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

Это использует гуавы в Multiset и math утилиты.