CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Синус. (57938 hits)
#Простая быстрая сортировка. (108610 hits)
#Рисование линии. (36494 hits)
#Двусторонняя карта. (31523 hits)
#Поверхностное клонирование. (25629 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (29054 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (43664 hits)
#Сравнение алгоритмов быстрой сортировки. (71124 hits)
#Вычисление медианы заданной выборки. (47222 hits)
#Просмотр изображения во всплывающем окне. (86327 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (252407 hits)
#Плоттеры для рисования графиков. (27867 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (55842 hits)
#Работа с камерой. (33679 hits)
#сортировка пузырьком. (148993 hits)
#Вставка новой записи в таблицу БД. (34506 hits)
#Использование компилируемых (prepared) запросов. (28493 hits)
#Таймер. (38634 hits)
#Сохранение данных формы после перезагрузки через куки. (195831 hits)
#Программное создание ссылок. (97498 hits)


Главная >> Каталог задач >>

Посчитать количество пар чисел (number of equal pairs)

Aвтор:
Дата:
Просмотров: 681
реализации(java: 2шт...) +добавить

Постановка задачи

Вот есть у нас всего N чисел и как нам наиболее быстро посчитать количество одинаковых в нем пар чисел (number of equal pairs)?
Задача выглядит довольно простой, на самом же деле для поиска оптимального решения придется применить комбинаторные формулы предварительно упростив их для частного случая(!).

Решение в "лоб" (перебором)

Для простого и интуитивного решения особо никакие формулы не понадобятся, используем т.н. метод "перебора" т.е. сначала в цикле перебираем все N чисел и на каждом шаге запускаем еще один внутренний цикл по всем числам начиная от текущего, проверяя равные пары и увеличивая их итоговое кол-во:

 псевдокод: Подсчет одинаковых пар чисел перебором, квадратичная сложность  ссылка
  1. arr=<наш исходный массив чисел>
  2. res = 0;
  3. for (i = 0...N-1) {
  4. for (j = i+1...N-1) {
  5. if ( i != j && arr[i] == arr[j]) {
  6. res++
  7. }
  8. }
  9. }

Обратите внимание что вложенный цикл начинается не с нуля (т.е. не с начала массива!) а с элемента следующего за текущим (i+1) и это важно т.к. нам нужно посчитать количество уникальных пар, т.е. Комбинаций (или сочетаний, combination) элементов фактически, а не Перестановок (или размещений, partial permutations) (пошла уже комбинаторика, но - спокойно, пока не вдаваться не будем).

Решение на java будет выглядеть вот так.

Оптимальное решение

Ну что ж, с методом перебора (что медленно и плохо) разобрались, давайте уж рассмотрим оптимальный алгоритм.
Как-бы нам так оптимизировать чтобы за несколько проходов по массиву посчитать равные пары... Вообще возможно ли это на исходном массиве? Без дополнительных структур данных для хранения промежуточных результатов - очевидно что нет.

Поэтому размышляя дальше и учитывая что нам нужно только посчитать пары без сохранения массива в исходном виде, то может реально как-то преобразовать сначала исходные данные для удобства? Ну учитывая что нам нужно посчитать только равные пары, то если они будут расположены вплотную к друг другу - считать их будет гораздо проще.
Действительно, а как это проще сделать без вложенных циклов? Правильно - сортировка!
Ведь после сортировки все одинаковые числа будут расположены рядом с друг другом. Например, если мы имели такой массив: [2,5,7,5,3,9,4,7] то после сортировки это будет [2,3,4,5,5,7,7,9] - и нам только остается посчитать пары внутри рядов 5-ок и 7-рок. 

Уже гораздо эффективней и вложенные циклы вроде не понадобятся, т.к. задача к сводится к подсчету пар среди одинаковых чисел, т.е. если имеем 3 пятерки (5,5,5) - то всего из них будет 3 уникальные пары чисел (1я пятерка со второй, 2я с 3й и 1я с 3й), но постойте... - ничего не напоминает? Что там было про комбинаторику? :-) 

Да, именно! это тот же подсчет Комбинаций (или сочетаний, combination) только в частном случае для пары чисел:

{n \choose k}=C_{n}^{k}={\frac {n!}{k!\left(n-k\right)!}}.

Т.е. k = 2 т.к. ищем пару, а n = количеству одинаковых чисел, т.е. в нашем случае 3х пятерок это будет 3.

Ок, отлично, нашли быстрый способ, т.е. после сортировки мы идем в цикле по сортированному массиву, и для каждого фрагмента с одинаковыми числами применяем эту формулу подставляя k=2 n=<размер фрагмента> и наш алгоритм будет примерно выглядеть как:

 псевдокод: Подсчет одинаковых пар, наброски быстрого алгоритма  ссылка
  1. arr=<наш исходный массив чисел>
  2. sort(arr) // сортируем
  3. res = 0
  4. for (i = 1...N-1) {
  5. if (arr[i] == <конец фрагмента равных чисел>)
  6. res = res + <формула комбинаций при k=2 n=размер фрагмента>
  7. }

Круто! Почти почти всё готово для финального решения, но только есть момент: формула подсчета комбинаций довольно непростая и содержит факториалы(!), для которых обычно нет встроенных функций в языках программирования, а ручной подсчет факториала - создаст те же самые вложенные циклы и сведет на нет все преимущества найденного решения...
Как же быть, т.е. как оптимизировать теперь подсчет факториалов?

Формула!

Спокойно... у нас же k = 2, далее - а что будет если подставить это в формулу и учитывая суть факториала немного разделить его на составляющие множители? Например так:

n! / (2! * (n-2)!) = (n-2)! * (n-1) * n / ( 2 * (n-2)! )

Интересно... одинаковые части вверху и внизу множителя сокращаются и это же все превращается в: 

(n-1) * n / 2

Класс! Т.е. никакие факториалы уже считать не понадобится и остается предельно простая формула!

Псевдокод

Итак, все понятно, со всем разобрались, давайте теперь составим итоговый псевдокод данного решения.
Для подсчета пар которые идут подряд после сортировки заведем отдельную переменную currPairs с начальным значением 1 (что соответствует n в формуле комбинаций, т.е. множество из 1 числа, начальный случай).
Далее идем в цикле по отсортированному массиву и если находим повторы то увеличиваем currPairs на единицу, если же следующее значение массива меняется, то применяем нашу формулу для подсчета накопленных пар где n = currPairs, в итоге получится как-то так: 

 псевдокод: Быстрый алгоритм подсчета одинаковых пар  ссылка
  1. arr=<наш исходный массив чисел>
  2. sort(arr) // сортируем
  3. res = 0
  4. currPairs = 1
  5. for (i = 1...N-1) do:
  6. if arr[i] == arr[i-1] then:
  7. currPairs = currPairs + 1
  8. else:
  9. if currPairs > 1 then:
  10. res = res + (currPairs - 1)*currPairs / 2 // наша формула
  11. currPairs = 1 // обнуляем для следующего раза
  12. end // конец цикла
  13.  
  14. // тут важный момент для случая когда равные числа в конце, но цикл-то уже закончился,
  15. // т.е. снова придется считать по формуле:
  16. if currPairs > 1 then:
  17. res = res + (currPairs - 1)*currPairs / 2
  18.  
  19. return res // итоговый результат в этой переменной

Обратите внимание на финальный пересчет после окончания цикла, давайте разберем в каком случае это понадобится, для начала обычный случай т.к. если отсортированный массив (после 1й строки) выглядит как arr=[1,3,3,3,3,4,5,6,6,6,8,10,15] - то в цикле мы уже корректно посчитаем все 3-ки и 6-ки и после его завершения ничего досчитывать не понадобится. Но вот если одинаковые числа идут в конце например как arr=[1,3,3,3,3,4,5,6,8,9,9,9] то давайте подумаем что будет после завершения цикла: переменная currPairs = 3 (после подсчета всех 9-ток), но т.е. цикл завершился и после 9-ток не было смены числа то к итоговому результату в res мы это не добавили, поэтому приходится повторять if проверку, досчитывать по формуле (строки 16-17).

Код на java

Применив небольшую оптимизацию в виде лямбда функции для подсчета формулы и избежав тем самым дублирование кода пересчета после цикла - код финального решения на языке java будет выглядеть так:

 Как посчитать количество пар чисел в массиве, быстрый алгоритм [java]  ссылка
  1. import java.util.Arrays;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Optional;
  5. import java.util.function.IntFunction;
  6.  
  7. class EqualPairCounter {
  8.  
  9. int numberOfEqualPairsLinearithmic(int[] a) {
  10. Arrays.sort(a);
  11. int res = 0;
  12. int currPairs = 1;
  13. IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
  14. for (int i = 1; i < a.length; i++) {
  15. if (a[i] == a[i - 1]) {
  16. currPairs++;
  17. } else {
  18. res += countFn.apply(currPairs);
  19. currPairs = 1;
  20. }
  21. }
  22.  
  23. res += countFn.apply(currPairs);
  24. return res;
  25. }
  26.  
  27. public static void main(String[] args) {
  28. int[] arr = {1, 2, 4, 1, 2, 1, 2, 4, 5, 1, 2, 4, 5, 1, 2 ,5, 6, 7, 7, 8, 2, 1, 2, 4, 5};
  29. int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
  30. System.out.printf("Res: %s", pairCount); // => 49
  31. }
  32. }
Полный код...

Выводы

В этой задачи мы рассмотрели сначала медленный но простой вариант O(N^2), потом же ускорили его до линейно-алгорифмичного и в итоге без каких либо доп расходов кроме сортировки выработали алгоритм с производительностью O(N*Lg(N)) способный решить задачу не только на массиве но и любом другом списке с последовательным доступом (list, set и тд.).

Круто, а есть еще варианты, может еще быстрее можно? Да, есть! Но об этом - уже в следующей части.

Реализации:

java(2)   +добавить

1) Найти все одинаковые пары чисел в массиве перебором на java, code #797[автор:this]
2) Быстрый подсчет одинаковых пар чисел (number of equal pairs) на java, code #800[автор:this]