[только оператор равенства] Каковы быстрые алгоритмы, чтобы найти дубликаты элементов в коллекции и сгруппировать их?

Question

[только оператор равенства] Каковы быстрые алгоритмы, чтобы найти дубликаты элементов в коллекции и сгруппировать их?

Предположим, у нас есть набор элементов, и эти элементы имеют только одинаковый оператор. Таким образом, невозможно отсортировать их.

как выбрать тех, у кого есть дубликаты, и поместить их в каждую группу с наименьшим количеством сравнений? желательно на С ++, но алгоритм важнее языка. Для примера, данного {E1, E2, E3, E4, E4, E2, E6, E4, E3}, я хочу извлечь {E2, E2}, {E3, E3}, {E4, E4, E4}. какую структуру данных и алгоритм вы выберете?

РЕДАКТИРОВАТЬ

Мой сценарий, если двоичные данные 1 равны двоичным данным 2, мы можем сказать, что эти два элемента идентичны. Но только знак равно а также !знак равно логично

element 1:

4 0 obj
<< /Type /Pages /Kids 5 0 R /Count 1 >>
stream
.....binary data 1....
endstream
endobj

element 2:

5 0 obj
<< /Type /Pages /Kids 5 0 R /Count 1 >>
stream
.....binary data 2....
endstream
endobj

1

algorithm c++genetic-algorithm stl-algorithm

Решение

Другие решения

Для вашего ответа, хотя я не уверен на 100%, что вы хотите, это только.

Если хочешь хорошего, попробуй Binary search tree создание. как это группа, и в соответствии с BST properties Вы можете легко сгруппировать элементы.

Например

BST()
{
count = 0;
if(elementinserted)
count = 1;
if(newelement == already inserted element)
{
count++;
put element in array upto count value;
}
}

Я надеюсь, что это объяснение может помочь вам.

2

Если у вас есть только тест на равенство, у вас нет надежды.

Предположим, у вас есть ситуация, когда каждый элемент уникален. И еще один, где только два элемента являются дубликатами.

Есть n(n+1)/2 второго типа. Каждое из них можно отличить только от первого по определенному сравнению. Что означает, что в худшем случае вы должны сделать все n(n+1)/2 Сравнения: исчерпывающий поиск по всем парам.

Что вам нужно сделать, это выяснить, что еще вы действительно можете сделать, поскольку равенство исключительно редко.

2

Источник

Accepted Answer

Достаточно найти любой произвольный предикат P такой, что P(a,a)==false, P(a,b) && P(b,a)==false, P(a,b) && P(b,c) подразумевает P(a,c) а также !P(a,b) && !P(b,a) подразумевает a == b, Меньше — тогда удовлетворяет этому свойству, как, таким образом, больше — тогда. Но они далеко не единственные возможности.

Теперь вы можете сортировать свою коллекцию по предикату Pи все равные элементы будут смежными. В вашем случае определите P(E1,E2)=true, P(E2,E3)=true, так далее.

3