2

Всем привет! У меня возникла небольшая проблема у меня имеется список с различными значениями в хаотичном порядке содержащим числа от 1 до 9. Мне нужно сделать проверку, если 3 значения в результате дадут 15. Числа не повторяются и массив не меньше чем три числа. Это вопрос аналогия поскольку будет использоваться более большие магические квадраты(так и называются - магические).

Я знаю что вопрос очень маленький но мне нечем его дополнить. :/

17
  • 1
    Простейший вариант решения - три вложенных цикла, каждый следующий начинается с индекса текущего элемента предыдущего цикла + 1. Сложить числа по индексам всех трёх циклов, проверить, что это 15, если да - вывести эти индексы. Ну, примерно так, с граничными значениями надо тщательно только разобраться. Всё.
    – CrazyElf
    19 июл 2021 в 18:53
  • 2
    @Alexalexeev вы сейчас пытаетесь купить эскаватор, чтобы вырыть себе маленькую ямку для посадки луковицы.
    – n1tr0xs
    19 июл 2021 в 19:25
  • 2
    Ну тогда и задавали бы вопрос-обобщение сразу, потому что решение для частного случая может совершенно не подходить для общего, как например то, которое я только что написал
    – EzikBro
    19 июл 2021 в 19:34
  • 1
    Я правильно понимаю, что в обобщенном варианте есть некоторый список, состоящий из некоторых уникальных чисел от 1 до N^2, и нужно выбрать из него N чисел таких, что их сумма равна сумме всех чисел от 1 до N^2, деленной на N (то есть N*(N^2+1)/2)?
    – EzikBro
    19 июл 2021 в 19:49
  • 1
    Для такого обобщения можно использовать некоторый аналог решения задачи о рюкзаке, итоговая сложность будет вроде O(N^6) - [сумма]*[кол-во чисел в наборе]*[кол-во чисел в списке]. Если вы подтвердите, что я правильно понял обобщение вашей задачи, то напишу ответ.
    – EzikBro
    19 июл 2021 в 20:10

3 ответа 3

3

Написал решение для общего случая:

def magic_support(dp, n, s=None, i=None, j=None, last=None):
    if s is None:
        s = n * (n ** 2 + 1) // 2
        i, j = n, s
        last = s + 1

    elif i == 0:
        yield []
        return
    
    for item in dp[i][j]:
        if item >= last:
            break
        for res in magic_support(dp, n, s, i - 1, j - item, item):
            yield res + [item]


def magic(a, n):
    a.sort()
    s = n ** 2 * (n ** 2 + 1) // 2 // n # 3: 15, 4: 34
    
    dp = [[[] for _ in range(s + 1)] for _ in range(n + 1)]
    dp[0][0] = [0]
    for item in a:
        for layer in range(n - 1, -1, -1):
            for weight in range(s - item + 1):
                if dp[layer][weight]:
                    dp[layer + 1][weight + item].append(item)
    
    return magic_support(dp, n)


n = 4
a = [1, 3, 5, 6, 7, 10, 12, 13]
for i in magic(a, n):
    print(i)
# [5, 7, 10, 12]
# [5, 6, 10, 13]
# [3, 6, 12, 13]

В основе алгоритма лежит ДП-решение задачи о рюкзаке. Только в данном случае предметы не имеют никакой ценности, вычисляется только принципиальная возможность собрать рюкзак определенного веса. dp[layer][weight] отвечает на вопрос, возможно ли собрать сумму weight из layer предметов. В каждой ячейке массива dp хранится список из чисел, используя которые можно ее достичь. Благодаря этому, возможно восстановить "путь", которым была собрана сумма s.

Функция magic работает за O(N^6), но количество путей растет очень быстро. В массиве оно хранится достаточно сжато, но я за полчаса так и не дошел до конца генератора при N=20. Знаю лишь то, что при N=11, все двадцать миллионов комбинаций перебирались две минуты.

Перебор для малых значений N, по моему мнению, проще всего пишется так:

from itertools import combinations

n = 4
s = 34
a = [1, 3, 5, 6, 7, 10, 12, 13]
for comb in combinations(a, n):
    if sum(comb) == s:
        print(*comb)
# 3 6 12 13
# 5 6 10 13
# 5 7 10 12

Но это решение не оптимально по своей скорости, поэтому я попробовал написать рекурсивный перебор с отсечением ветвей:

def rec(a, n, s=None, count=0, last=-1, summ=0, way=None):
    if count == 0:
        a.sort()
        s = n * (n ** 2 + 1) // 2
        way = []
        
    elif count == n:
        if summ == s:
            yield way
        return

    elif summ + (n - count) * a[last] > s:
        return
    
    for i in range(last + 1, len(a) - n + count + 1):
        way.append(a[i])
        yield from rec(a, n, s, count + 1, i, summ + a[i], way)
        way.pop()


n = 4
a = [1, 3, 5, 6, 7, 10, 12, 13]
for i in rec(a, n):
    print(i)
# [3, 6, 12, 13]
# [5, 6, 10, 13]
# [5, 7, 10, 12]
3
  • спасибо тебе! :D 20 июл 2021 в 17:44
  • ей а можешь подсказать как сделать так что бы он находил все возможные комбинации. 21 июл 2021 в 13:38
  • @Alexalexeev переделал решение, теперь выдает все комбинации. Возможно завтра еще отредактирую код, потому что сейчас сонный и не уверен до конца.
    – EzikBro
    21 июл 2021 в 22:28
3

Ладно, вот вам более рациональный способ:

def magic(a):
    in_a = [False] * 10
    for i in a:
        in_a[i] = True
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            x = 15 - a[i] - a[j]
            if x > 0 and in_a[x] and x != a[i] and x != a[j]:
                return [a[i], a[j], x]
    return []

print(magic([2, 4, 9, 1, 6]))
# [2, 4, 9]

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

Работает не за N^3/6 как в полностью переборном алгоритме, а за N^2/2, но в вашем случае (размер массива до девяти) выигрыш будет не более, чем в два раза.

1

Общий подход для любого кол-ва элементов/размера пачки для суммы/суммы.

import typing as t
import random

def magic(array: list, cnt: int, sum_: int) -> t.List[list]:
    """

    :param array:  массив элементов
    :param cnt:  размер пачки элементов для проверки
    :param sum_:  суммма пачки которая делает ее "магической"
    :return: массив магических пачек.
    """
    result = []
    if len(array) < cnt:
        raise ValueError("Список меньше заданного кол-ва чисел.")

    slice_count = len(array) - cnt + 1
    chunks = [
        array[i:i + cnt]
        for i in range(slice_count)
    ]

    for chunk in chunks:
        if sum(chunk) == sum_:
            result.append(chunk)

    return result


arr = [1, 2, 7, 9, 5, 2, 5, 3, 2, 4, 1, 5, 3]
print([[1, 2, 7], [2, 5, 3], [5, 3, 2], [4, 1, 5]] == magic(arr, 3, 10)) # out: True
print([[2, 7, 9, 5, 2]] == magic(arr, 5, 25))  # out: True

arr_2 = [1, 3, 5, 11, 9, 7, 14, 6, 8, 12]

for i in magic(arr_2, 2, 20):
    print(f"Magic chunk - {i}")
# out: Magic chunk - [11, 9]
#      Magic chunk - [14, 6]
#      Magic chunk - [8, 12]
arr_3 = [random.randint(x, x * 2 - x % 2) for x in range(1_000_000)]

start = datetime.now()
for i in magic(arr_3, 8, 124):
    print(f"Magic chunk - {i}")
print(f'get magic for {datetime.now() - start}')
# out:
#Magic chunk - [8, 16, 17, 10, 16, 22, 14, 21]
#get magic for 0:00:00.736550

Единственное, не стал заморачиваться с проверкой на уникальные значения, алгоритм не изменится - можете добавить сами в начале функции. Скорость зависит от cnt. Чем выше тем меньше пачек, но дольше занимает сумма элементов. + При очень больших значениях и большом cnt я бы вынес формирование пачек в отдельную функцию с генератором что бы не хранить их в памяти, да и сам результат если предполагается много магических последовательностей лучше генерировать..

1
  • спасибо большое!) 20 июл 2021 в 8:18

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.