python функция combinations

Question

from itertools import combinations
x = [1, 2, 3, 4]
list(combinations(x, 2))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

У меня есть список состоящий из 4 чисел. Мне нужно узнать все пары из этих чисел и после узнать какие из этих пар по сумме равны между друг собой и какое количество таких пар.

Например, для примера на скриншоте получилось 6 пар, из них я могу выделить пару 1, 4 и 2, 3, ведь их суммы будут равны, если я правильно посчитал, то больше таких пар нет и в итоге в выводе я должен получить 1.

Можно ли как-то взять из этой функции все пары и после сравнить их суммы или нет? Или может это можно сделать как-то по другому, вовсе не использую эту функцию? Да, я конечно мог бы просто посчитать все пары, потом посчитать их суммы и сравнить, но как минимум это дольше, а как максимум чисел может быть не 4, а 14 или еще больше.

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

Возможно я вообще не в ту сторону иду, и всё может оказаться куда легче... (Я хочу сделать это задание конкретно через python, а не excel)

Answer 1

Простое решение которое вижу я:

Создаём словарь, где ключ - результат сложение, а значение - список пар чисел, которые в сумме дают это самое значение

x = [1, 2, 3, 4]
combs = list(combinations(x, 2))

result = {} # Создаём словарь
for comb in combs: # Для каждой комбинации
    s = comb[0] + comb[1] # получаем её сумму

    if s in result: # Если такая сумма уже существует
        result[s].append(comb) # Добавляем комбинацию
    else: # Иначе
        result[s] = [comb] # Создаём новый список с комбинацией comb

В итоге получаем такой список:

{3: [(1, 2)], 4: [(1, 3)], 5: [(1, 4), (2, 3)], 6: [(2, 4)], 7: [(3, 4)]}

Теперь мы можем просто определить, у какого ключа больше всего список:

max(result, key=lambda comb: len(result[comb])) # 5

Сложность алгоритма выходит O(n) где n - количество комбинаций (если не учитывать обращения к словарю)

Answer 2

В части нахождения пар с одинаковой суммой:

анализируем сумму четырех чисел - если она нечетная, то пар нет;
если четная, то берем полусумму;
берем первое число и отнимаем его от полусуммы (разница);
пытаемся найти разницу среди оставшихся 3-х чисел;
если находим, то ставим галку - 2 пары есть.

from random import randint

lst = [[randint(1, 10) for _ in range(4)] for _ in range(20)]
cnt = 0
for l in lst:
    s = sum(l)
    if s % 2 == 0:
        if s // 2 - l[0] in l[1:]:
            cnt += 1
            print(f"{l} cодержит 2 пары с суммой = {s // 2}")
print(f'Всего строк с парами с равной суммой = {cnt}')

[4, 4, 4, 4] cодержит 2 пары с суммой = 8
[1, 2, 2, 1] cодержит 2 пары с суммой = 3
[4, 5, 1, 8] cодержит 2 пары с суммой = 9
[5, 10, 9, 6] cодержит 2 пары с суммой = 15
[4, 5, 7, 8] cодержит 2 пары с суммой = 12
Всего строк с парами с равной суммой = 5

Answer 3

Я исхожу из вопроса, который Вы предоставили в задании и который стоял перед Вами изначально. четыре числа разбить на две пары чисел с равными суммами. Что делает combinations: возвращает все возможные пары. Но какой смысл сравнивать пары, в которых участвуют одни и те же цифры - это не будет верным решением. Пример:

[1, 3, 3, 4]

С помощью combinations мы получим две пары (1, 3), и такая последовательность подойдет нам. Но это неверно, так как мы два раза использовали одно и тоже число 1, а судя по условию, мы не можем так делать. Поэтому, решение конкретно Вашей задачи (а не задачи с неизвестным количеством чисел в списке), мне кажется будет решением в лоб. У нас есть всего три возможных пары с индексами [(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]. Других пар пар в последовательности из четырех чисел нет. Вот и надо написать функцию, которая сравнит эти три пары по суммам.

Answer 4

Для решения данной конкретной задачи:

Находим сумму четырёх чисел S

Находим максимум и минимум MX, MN

Проверяем, что (MX + MN)*2 == S.

При выполнении этого условия другое условие S - MX > MX для натуральных чисел будет удовлетворено автоматически, как заметил Алексей Р.

БЛОГ НА HUSL

python функция combinations

Ответы (4 шт):