Информатика · ЕГЭ · 4 мин чтения

Как перебрать все пары без повторов во вложенных циклах?

Редакция Алгоса · Обновлено

Короткий ответ

Для всех пар разных элементов без учёта порядка выбирай индексы i и j так, чтобы i < j. Внешний цикл перебирает i, внутренний — значения j от i + 1 до конца списка. Тогда элемент не соединяется сам с собой, а пара не появляется второй раз в обратном порядке.

Разберись, что нужно найти

Индекс — номер позиции в списке, начиная с нуля. Даже если значения совпадают, позиции могут быть разными. В списке [5, 5, 8] первые две пятёрки находятся на разных местах и образуют допустимую пару позиций. Поэтому условие a[i] != a[j] не заменяет требование разных индексов: оно решает другую задачу.

Связь условия задачи с нужным действием
Что дано или требуетсяКак это использовать
i < jВсе неупорядоченные пары разных позиций
i ≠ jУпорядоченные пары разных позиций
j = i + 1Только соседние пары

Проследи решение на конкретных данных

Для четырёх элементов с индексами 0, 1, 2, 3 при i = 0 внутренний цикл берёт 1, 2, 3. При i = 1 остаются 2 и 3, при i = 2 — только 3. При i = 3 подходящих j нет. Всего получаем 3 + 2 + 1 = 6 пар.

Промежуточные результаты разобранного примера
ШагРезультат
i = 0j = 1, 2, 3
i = 1j = 2, 3
i = 2j = 3
Пример с объяснением
Код для списка a = [2, 4, 7, 9]:
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        print(a[i], a[j])
Будут выведены пары 2 4; 2 7; 2 9; 4 7; 4 9; 7 9. Верхняя граница range не включается, поэтому индекс len(a) не появится.

Проверь границы способа и реши сам

Если порядок важен, ограничение i < j уже лишнее: пары (2, 4) и (4, 2) считаются разными. Тогда можно перебрать все i и j, исключив только i = j. Также не путай все пары с соседними: при n ≥ 1 соседних пар в списке из n элементов лишь n − 1, а всех неупорядоченных — n(n − 1)/2.

Самопроверка: сколько пар разных позиций будет у списка из пяти элементов при i < j? Сколько из них соседние? Проверь отдельно пустой список и список из одного элемента: должно ли происходить хотя бы одно выполнение внутреннего тела?

Ответ и почему так

Всех пар будет 5 × 4 / 2 = 10, соседних — 4. У пустого списка и списка из одного элемента пар разных позиций нет. Условия циклов это обеспечивают без обращения к несуществующим элементам: внутренний диапазон каждый раз оказывается пустым.

Что запомнить

Для неупорядоченных пар разных позиций используй i < j: так нет самопар и повторов в обратном порядке.

Попробовать на Алгосе

Программирование для ЕГЭ

Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы