Разбить массив на пары

Есть допустим массив с повторяющимися элементами arr[1,1,1,1,1,1,2,2,2,3,3,4,5,6]. Нужно разбить на пары, где каждая пара состоит из уникальных элементов с разными значениями. Каждый элемент может использоваться только в одной паре!

То есть arr[0] и arr[1] уникальные элементы, но пару из них делать нельзя т.к. имеют одно значение. В то же время можно сделать пары &arr&0], arr[6]] и &arr&1], arr[7]], т.е. [1,2] и [1,2]. Можно потому что хоть две пары и одинаковые по значению, сами элементы (arr[0], arr[6], &arr&1], arr[7]) уникальны.

Результат после разбиения вышеприведенного массива должен быть например [1,2],[1,2],[1,3],[1,4],[1,5],[1,6],[2,3]].

Я сделал через группировку, сортировку desc по количеству элементов в группе, и проходу по группам и элементам c выбрасыванием использованных элементов. Интересны ваши решения.

P.S.в одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто-то разжует можно тут по массиву с помощью какой нибудь формулы прикольной это узнать или нельзя.

Как обычно, в математике 0.

UPD: сори, ошибся в условии. Обновил. Две пары могут быть одинаковыми по значениям, важно чтобы эти значения принадлежали разным элементам массива.

использовать словари?

Ну тут @KeksovName звать надо, Ну ка кекс объясни молодому как это делается

ttutiki сказал(а):↑

Есть допустим массив с повторяющимися элементами arr[1,1,1,1,1,1,2,2,2,3,3,4,5,6]. Нужно разбить на неповторяющиеся пары, где каждая пара состоит из уникальных элементов с разными значениями.

То есть arr[0] и arr[1] уникальные элементы, но пару из них делать нельзя т.к. имеют одно значение.

Результат должен быть например [1,2],[1,3],[1,4],[1,5],[1,6],[2,3]]. 1 и 2 остались вне пар.

Я сделал через группировку, сортировку desc по количеству элементов в группе, и проходу по группам и элементам c выбрасыванием использованных элементов. Интересны ваши решения.

В одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто разжует можно это тут сделать или нельзя.

Как обычно, в математике 0.

Нажмите, чтобы раскрыть...

Раздели на 2

vdz сказал(а):↑

Раздели на 2

Нажмите, чтобы раскрыть...

ты сам то попробовал на моем примере разделить на 2?)

[1,1,1,1,1,1,5] 1 пара [1,5] для наглядности

А что тебе нужно то? Ты же и так уже предложил решение? Или нужно разбить так, чтобы получилось максимальное возможное количество пар?

HealSlut сказал(а):↑

А что тебе нужно то? Ты же и так уже предложил решение? Или нужно разбить так, чтобы получилось максимальное возможное количество пар?

Нажмите, чтобы раскрыть...

ну покрасивше побыстрее, у меня то из говна и палок я думаю, ну и максимальное количество пар тоже будет хорошо

public static List splitToPairs(int[] arr) {
 List pairs = new ArrayList<>();
 Map usedFirst = new HashMap<>();
 for (int i = 0; i < arr.length; i++) {

 int number = arr;

 if (!usedFirst.containsKey(number)) {


 usedFirst.put(number, false);

 }

 usedFirst.put(number, true);
 }
 for (int number : usedFirst.keySet()) {

 if (usedFirst.get(number)) {


 for (int otherNumber : usedFirst.keySet()) {

if (otherNumber != number && usedFirst.getOrDefault(otherNumber, false)) {

pairs.add(new Pair(number, otherNumber));

}

}

}

}

return pairs;

} Хз как тут форматирвоать, ну алиса решила типа хз правильно или нет

ttutiki сказал(а):↑

ну покрасивше побыстрее, у меня то из говна и палок я думаю, ну и максимальное количество пар тоже будет хорошо

Нажмите, чтобы раскрыть...

Я думаю, если сделать то что ты делал:

ttutiki сказал(а):↑

Я сделал через группировку, сортировку desc по количеству элементов в группе, и проходу по группам и элементам c выбрасыванием использованных элементов. Интересны ваши решения.

Нажмите, чтобы раскрыть...

Но при этом объединять в пару элементы из перых двух групп и после объединения обновлять упорядоченность по количеству элементов, то должно получиться максимальное количество пар.

import itertools

set_arr = set(arr)

pairs = list(itertools.combinations(set_arr, 2))

print(pairs)

ttutiki сказал(а):↑

Есть допустим массив с повторяющимися элементами arr[1,1,1,1,1,1,2,2,2,3,3,4,5,6]. Нужно разбить на неповторяющиеся пары, где каждая пара состоит из уникальных элементов с разными значениями.

То есть arr[0] и arr[1] уникальные элементы, но пару из них делать нельзя т.к. имеют одно значение.

Результат должен быть например [1,2],[1,3],[1,4],[1,5],[1,6],[2,3]]. 1 и 2 остались вне пар.

Я сделал через группировку, сортировку desc по количеству элементов в группе, и проходу по группам и элементам c выбрасыванием использованных элементов. Интересны ваши решения.

В одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто разжует можно это тут сделать или нельзя.

Как обычно, в математике 0.

Нажмите, чтобы раскрыть...

напиши себе алгоритм да и делов то, все в прогерстве решается этим https://www.ozon.ru/product/kniga-tomas-kormen-charlz-leyzerson-ronald-rivest-klifford-shtayn-algoritmy-postroenie-i-analiz-3-611740877/?sh=ywoR5-LRcA

ttutiki сказал(а):↑

ты сам то попробовал на моем примере разделить на 2?)

[1,1,1,1,1,1,5] 1 пара [1,5] для наглядности

Нажмите, чтобы раскрыть...

А перестановки за уникальность не счиаеться? Тк 5,1

haHAA сказал(а):↑

import itertools

set_arr = set(arr)

pairs = list(itertools.combinations(set_arr, 2))

print(pairs)

Нажмите, чтобы раскрыть...

import itertools

arr = [1,1,1,1,1,1,2,2,2,3,3,4,5,6]

set_arr = set(arr)

pairs_v1 = list(itertools.combinations(set_arr, 2))

pairs_v2 = [(j, i) for i, j in pairs_v1]

print(pairs_v1 + pairs_v2)

можно так если перестановка мест в паре считается за новую пару

Результат очень похож на матрицу смежности

Предполагаю, что выполнимо за один проход

ttutiki сказал(а):↑

ты сам то попробовал на моем примере разделить на 2?)

[1,1,1,1,1,1,5] 1 пара [1,5] для наглядности

Нажмите, чтобы раскрыть...

[0.5,0.5,0.5,0.5,0.5,0.5,2.5] не благодари

ttutiki сказал(а):↑

Есть допустим массив с повторяющимися элементами arr[1,1,1,1,1,1,2,2,2,3,3,4,5,6]. Нужно разбить на неповторяющиеся пары, где каждая пара состоит из уникальных элементов с разными значениями.

То есть arr[0] и arr[1] уникальные элементы, но пару из них делать нельзя т.к. имеют одно значение.

Результат должен быть например [1,2],[1,3],[1,4],[1,5],[1,6],[2,3]]. 1 и 2 остались вне пар.

Я сделал через группировку, сортировку desc по количеству элементов в группе, и проходу по группам и элементам c выбрасыванием использованных элементов. Интересны ваши решения.

В одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто разжует можно это тут сделать или нельзя.

Как обычно, в математике 0.

Нажмите, чтобы раскрыть...

так у тебя массив заранее отсортирован, один проход циклом ты вычищаешь повторяющиеся элементы, второй проход собираешь пары

Спойлер

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

KRATI сказал(а):↑

так у тебя массив заранее отсортирован, один проход циклом ты вычищаешь повторяющиеся элементы, второй проход собираешь пары

Спойлер

Нажмите, чтобы раскрыть...

так в примере просто получилось, в реале не отсортирован он

KRATI сказал(а):↑

так у тебя массив заранее отсортирован, один проход циклом ты вычищаешь повторяющиеся элементы, второй проход собираешь пары

Спойлер

Нажмите, чтобы раскрыть...

так и не то у тебя. на скрине в массиве тройки три, а в результате получилось пар с тройками болльше чем три

Данил Низамов сказал(а):↑

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

Нажмите, чтобы раскрыть...

не понимаю как тут хеш таблицы помогают, можешь подробнее расписать?

Nubiroed сказал(а):↑

напиши себе алгоритм да и делов то, все в прогерстве решается этим https://www.ozon.ru/product/kniga-tomas-kormen-charlz-leyzerson-ronald-rivest-klifford-shtayn-algoritmy-postroenie-i-analiz-3-611740877/?sh=ywoR5-LRcA

Нажмите, чтобы раскрыть...

прикольно выглядит книга, может задушусь и поизучаю

ttutiki сказал(а):↑

так и не то у тебя. на скрине в массиве тройки три, а в результате получилось пар с тройками болльше чем три

Нажмите, чтобы раскрыть...

пахахаха чел да ты поплыл вообще. на скрине в массиве две "3", а ты пишешь что их три, хотя этот массив ты сам привел

в результате их больше чем три. 1 3, 2 3, 3 4, 3 5, 3 6, я боюсь что это правильный вывод

ttutiki сказал(а):↑

так в примере просто получилось, в реале не отсортирован он

Нажмите, чтобы раскрыть...

ну так используй структуру Set. если тебе не важен порядок пак, то можешь отбросить сортировку, повторяться там ничего не будет

Спойлер

KRATI сказал(а):↑

пахахаха чел да ты поплыл вообще. на скрине в массиве две "3", а ты пишешь что их три, хотя этот массив ты сам привел

в результате их больше чем три. 1 3, 2 3, 3 4, 3 5, 3 6, я боюсь что это правильный вывод

ну так используй структуру Set. если тебе не важен порядок пак, то можешь отбросить сортировку, повторяться там ничего не будет

Спойлер

Нажмите, чтобы раскрыть...

ну две, не суть, я про то что в парах у тебя больше элементов (троек в данном случае) чем в массиве, чего быть не должно

ttutiki сказал(а):↑

ну две, не суть, я про то что в парах у тебя больше элементов (троек в данном случае) чем в массиве, чего быть не должно

Нажмите, чтобы раскрыть...

хорошо напиши какие по твоему пары должны быть

KRATI сказал(а):↑

хорошо напиши какие по твоему пары должны быть

Нажмите, чтобы раскрыть...

так у меня ж ответ в теме,

дописал немного чтоб понятнее было

ttutiki сказал(а):↑

В одном из пробных моих вариантов нужно было узнать максимальное количество пар, но че то не смог. Пришлось отказаться от варианта. Интересно будет если кто разжует можно это тут сделать или нельзя.

Нажмите, чтобы раскрыть...

И разбить на пары и сказать сколько максимум пар может быть? Или просто вывести формулу, которая по входным данным сможет сказать какое максимальное кол-во пар может быть, но при этом не будет разбивать их на пары?

DeadLuck сказал(а):↑

И разбить на пары и сказать сколько максимум пар может быть? Или просто вывести формулу, которая по входным данным сможет сказать какое максимальное кол-во пар может быть, но при этом не будет разбивать их на пары?

Нажмите, чтобы раскрыть...

ну вообще основная тема про алгоритм разбиения на пары, но еще было б интересно узнать реально ли посчитать максимальное количество пар не разбивая на пары да

я когда пытался что то нагуглить об этом в такие страшные формулы забурился и ливнул в итоге

ttutiki сказал(а):↑

ну вообще основная тема про алгоритм разбиения на пары, но еще было б интересно узнать реально ли посчитать максимальное количество пар не разбивая на пары да

я когда пытался что то нагуглить об этом в такие страшные формулы забурился и ливнул в итоге

Нажмите, чтобы раскрыть...

Я тебе могу одну идею подкинуть, но сам решения на вскидку не найду, в студенчестве смог бы быстро найти, но сейчас уже ничего не помню.

Не рассматривал задачу с точки зрения графов? Числа это вершины, а кол-во чисел это сколько максимум ребёр может быть у данной вершины.