Допустим, у меня следующие 6 пар чисел: 1 2 2 6 3 4 5

Question

Допустим, у меня следующие 6 пар чисел: 1 2 2 6 3 4 5

4
1 6
3 5
Мне нужно найти количество всех таких групп, где пары чисел будут связаны друг другом (не знаю, как правильно объяснить). Например, в примере выше тут две такие группы:
1 2
2 6
1 6
и
3 4
5 4
3 5.
То есть количество таких групп тут 2.
Есть ли какой-нибудь оптимальный способ найти такие группы, если количество таких пар будет где-то 100000?

#backend #programming #python #russian

0

19.07.2023

19 ответов

14 просмотров

Раскольников Автор вопроса

Vyacheslav @holydevlog
Ну т.е. в каждой группе 3 уникальных числа, так?

Нет. Может быть и группа вида: 1 2 2 3 1 4 3 4

0

19.07.2023

Vyacheslav @holydevlog

Раскольников
Нет. Может быть и группа вида: 1 2 2 3 1 4 3 4

А как ты определяешь сколько чисел будет в группе?

0

19.07.2023

Раскольников Автор вопроса

Vyacheslav @holydevlog
А как ты определяешь сколько чисел будет в группе?

Исходя из всех чисел. Просто нужно найти все циклы. Количество пар в одной группе не важно

0

19.07.2023

Vyacheslav @holydevlog

Раскольников
Исходя из всех чисел. Просто нужно найти все циклы...

причём здесь пары, группы ты по какому алгоритму формируешь?

0

19.07.2023

Сергей

Раскольников
Исходя из всех чисел. Просто нужно найти все циклы...

Вроде вот этот алгоритм

0

19.07.2023

Раскольников Автор вопроса

Vyacheslav @holydevlog
причём здесь пары, группы ты по какому алгоритму ф...

Я просто беру пару, беру одно из его чисел и ищу другую пару с таким же числом и так далее пока не вернусь к первой ппре. Например, при 1 2 2 6 3 4 5 4 1 6 3 5 Я беру первую пару (1, 2) и ищу пару с числом 2, потом беру второе число из найденной пары (2, 6), потом опять ищу новую пару со вторым числом (1, 6). Тут цикл замкнулся и получается первая группа. После ищу следующую пару не из этой группы.

0

19.07.2023

Раскольников Автор вопроса

Сергей
Вроде вот этот алгоритм

Благодарю. Прочитаю

0

19.07.2023

Vyacheslav @holydevlog

Раскольников
Я просто беру пару, беру одно из его чисел и ищу д...

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

0

19.07.2023

Tishka17

Vyacheslav @holydevlog
А, ну ты цепочку из пар строишь, ну тогда тебе над...

ну иногда цепочки будут объединяться же

0

19.07.2023

Раскольников Автор вопроса

Tishka17
ну иногда цепочки будут объединяться же

Забыл уточнить, что каждое число встречается только дважды

0

19.07.2023

Tishka17

Раскольников
Забыл уточнить, что каждое число встречается тольк...

ровно дважды или как?

0

19.07.2023

Владимир

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

0

19.07.2023

Владимир

Меня смущает такой момент что вроде бы на группы по разному можно разбить) и вот тут вопрос - тебя интересует минимальное количество групп?

0

19.07.2023

Сергей

Владимир
Меня смущает такой момент что вроде бы на группы ...

Разве группы это не компоненты связности? Только кажется не сильной как по ссылке выше а слабой но там вроде еще проще алгоритм..

0

19.07.2023

Раскольников Автор вопроса