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

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

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

Постановка задачи
Решение в "лоб" (перебором)
Оптимальное решение
Формула!
Псевдокод
Код на java
Выводы
Все реализации

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

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

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

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

псевдокод: Подсчет одинаковых пар чисел перебором, квадратичная сложность ссылка

arr=<наш исходный массив чисел>
res = 0;
for (i = 0...N-1) {
    for (j = i+1...N-1) {
        if ( i != j && arr[i] == arr[j]) {
            res++
        }
    }
}

arr=<наш исходный массив чисел>
res = 0;
for (i = 0...N-1) {
    for (j = i+1...N-1) {
        if ( i != j && arr[i] == arr[j]) {
            res++
        }
    }
}

Обратите внимание что вложенный цикл начинается не с нуля (т.е. не с начала массива!) а с элемента следующего за текущим (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=<размер фрагмента> и наш алгоритм будет примерно выглядеть как:

псевдокод: Подсчет одинаковых пар, наброски быстрого алгоритма ссылка

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

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

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

Формула!

Спокойно... у нас же 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, в итоге получится как-то так:

псевдокод: Быстрый алгоритм подсчета одинаковых пар ссылка

arr=<наш исходный массив чисел>
sort(arr) // сортируем
res = 0
currPairs = 1
for (i = 1...N-1) do:
   if arr[i] == arr[i-1] then:
     currPairs = currPairs + 1
   else:
     if currPairs > 1 then:
       res = res + (currPairs - 1)*currPairs / 2 // наша формула
       currPairs = 1 // обнуляем для следующего раза
end // конец цикла
 
// тут важный момент для случая когда равные числа в конце, но цикл-то уже закончился,
// т.е. снова придется считать по формуле:
if currPairs > 1 then:
  res = res + (currPairs - 1)*currPairs / 2
 
return res // итоговый результат в этой переменной

arr=<наш исходный массив чисел>
sort(arr) // сортируем
res = 0
currPairs = 1
for (i = 1...N-1) do:
   if arr[i] == arr[i-1] then:
     currPairs = currPairs + 1
   else:
     if currPairs > 1 then:
       res = res + (currPairs - 1)*currPairs / 2 // наша формула
       currPairs = 1 // обнуляем для следующего раза
end // конец цикла

// тут важный момент для случая когда равные числа в конце, но цикл-то уже закончился,
// т.е. снова придется считать по формуле:
if currPairs > 1 then:
  res = res + (currPairs - 1)*currPairs / 2

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] ссылка

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.function.IntFunction;
 
class EqualPairCounter {
 
    int numberOfEqualPairsLinearithmic(int[] a) {
        Arrays.sort(a);
        int res = 0;
        int currPairs = 1;
        IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                currPairs++;
            } else {
                res += countFn.apply(currPairs);
                currPairs = 1;
            }
        }
 
        res += countFn.apply(currPairs);
        return res;
    }
 
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
        System.out.printf("Res: %s", pairCount); // => 49
    }
}

Полный код...

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.function.IntFunction;

class EqualPairCounter {

    int numberOfEqualPairsLinearithmic(int[] a) {
        Arrays.sort(a);
        int res = 0;
        int currPairs = 1;
        IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                currPairs++;
            } else {
                res += countFn.apply(currPairs);
                currPairs = 1;
            }
        }

        res += countFn.apply(currPairs);
        return res;
    }
    
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
        System.out.printf("Res: %s", pairCount); // => 49
    }
}

Выводы

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

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

Реализации:

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

1) Найти все одинаковые пары чисел в массиве перебором на java, code #797[автор:this]

Подсчитать все пары чисел в массиве перебором ссылка |режим:

import java.util.Arrays;
import java.util.function.IntFunction;
 
class EqualPairCounter {
    int numberOfEqualPairsQuadratic(int[] arr) {
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (i != j && arr[i] == arr[j]) {
                    res++;
                }
            }
        }
        return res;
    }
 
    public static void main(String[] args) {
        int[] arr = new int[] {2,3,5,7,3,9,6,5,6,6,2,4,1,6,3};
        int pairCount = new EqualPairCounter().numberOfEqualPairsQuadratic(arr);
        System.out.printf("Res: %s", pairCount); // => 10
    }
}

import java.util.Arrays;
import java.util.function.IntFunction;

class EqualPairCounter {
    int numberOfEqualPairsQuadratic(int[] arr) {
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (i != j && arr[i] == arr[j]) {
                    res++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {2,3,5,7,3,9,6,5,6,6,2,4,1,6,3};
        int pairCount = new EqualPairCounter().numberOfEqualPairsQuadratic(arr);
        System.out.printf("Res: %s", pairCount); // => 10
    }
}

Находим все пары чисел которые равны медленным алгоритмом, перебирая исходный массив сначала во внешнем цикле и потом во внутреннем начиная с текущего элемента (подробней здесь), на выходе получаем конечно же квадратичную сложность, что плохо.
Если что - существует более быстрый алгоритм с линейно-логарифмической сложностью N*logN - подробней тут.

Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

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

Как посчитать количество пар чисел в массиве, быстрый алгоритм ссылка |режим:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.function.IntFunction;
 
class EqualPairCounter {
 
    int numberOfEqualPairsLinearithmic(int[] a) {
        Arrays.sort(a);
        int res = 0;
        int currPairs = 1;
        IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                currPairs++;
            } else {
                res += countFn.apply(currPairs);
                currPairs = 1;
            }
        }
 
        res += countFn.apply(currPairs);
        return res;
    }
 
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
        System.out.printf("Res: %s", pairCount); // => 49
    }
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.function.IntFunction;

class EqualPairCounter {

    int numberOfEqualPairsLinearithmic(int[] a) {
        Arrays.sort(a);
        int res = 0;
        int currPairs = 1;
        IntFunction<Integer> countFn = (cnt) -> cnt > 1 ? (cnt - 1) * cnt / 2 : 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                currPairs++;
            } else {
                res += countFn.apply(currPairs);
                currPairs = 1;
            }
        }

        res += countFn.apply(currPairs);
        return res;
    }
    
    public static void main(String[] args) {
        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};
        int pairCount = new EqualPairCounter().numberOfEqualPairsLinearithmic(arr);
        System.out.printf("Res: %s", pairCount); // => 49
    }
}

Оптимальное решение, классический метод без дополнительной памяти (не считая накладных расходов на сортировку) для подсчета одинаковых пар чисел в массиве за линейно-алгорифмичное время (N* Lg N).
При этом чтобы избежать дублирования формулу подсчета комбинаций выносим в лямбду функцию(countFn).

Тестировалось на: java-11-openjdk-amd64 @ubuntu20LTS

<< назад наверх

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

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

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

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

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

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

Формула!

Псевдокод

Код на java

Выводы

Реализации: