Математическая задача на перебор

Question

Даны цифры от 1 до 13 задача расположить их в таком порядке, чтобы следующее число делилось на сумму предыдущих и были использованы все числа и вывести все возможные варианты, пример: 8,4,2,7,1,11,3,9,5,10,12,6,13 , 4 делится на 8 , а 2 на сумму 4 и 8 и так далее. Наверное будет полезно знать, что сумма всех чисел составляет 91. Есть собственный код , но он очень громоздкий

Answer 1

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

Например, для начальной суммы 91 это 1,7,13. Если использовали в качестве последнего числа 1, то остаётся сумма 90 и подходят 2,3,5,6,9,10 и так далее.

Рекурсивно обрабатываем набор и сумму без выбранного числа.

Работает для данного количества мгновенно, оптимизировать дальше не стал (потенциал - формирование списка-решения, замена сета на битовый набор или что-то другое), 67 решений (пруф количества)

nums = set(range(1,14))
sm = sum(nums)
def work(nums, sm, ls = []):
    if sm==0:
        print(ls)
    else:
        for x in nums:
            if sm%x==0:
                 work(nums-{x}, sm-x, [x]+ ls)
work(nums, sm)

Answer 2

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

Первый вариант. Долгий, не практичный
В цикле while каждый раз вызываем рандомное число, далее создаем условия. Если сумма делиться на рандомное число без остатка, то записываем его в список. И прибовляем к сумме Если число уже есть в списке, или оно не делится без остатка на рандомное число, то пересаздаём число. Также нужно создать условие, на праверку дклимости всех доступных чисел. Чтобы небыло бесконечного пересоздания чисел. И при надобновсти он мог начать всё заного

И в конце условие. Если длина списка равн 13. Выводим список и пишем break

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

Второй вариант решения задачи:
Создаем 13 циклов фор, где будет происходить следующие действия: Прогоняем по списку, проверяя, если число было, то двигаемся дальше. Если число не делиться баз остатка, то двигаемся дальше. Если мы вернулись к первому цыклу фор, то список обновляем, сумму тоже. Если не поняли о чём я, то попробую примерно объяснить в следующем коде

L = [1,2,3,4,5,6,7,8,9,10,11,12,13]
L_rez = []
Sum = 0
For _1 in L:
    Sum = _1
    L_rez = [_1]
    For _2 in L:
        if Sum % 2 == 0 and _2 not in L_rez:
            L_rez.append(_2)
            Sum += _2
            for _3 in L:
                #и дальше в таком же темпе

Если что-то не правильно понял, извиняюсь

Есть еще такой вариан решения:

def is_valid_order(order):
    for i in range(1, len(order)):
        if order[i] % sum(order[:i]) != 0:
            return False
    return True
def generate_permutations(numbers):
    if len(numbers) == 1:
        return [numbers]
permutations = []
for i in range(len(numbers)):
    remaining = numbers[:i] + numbers[i+1:]
    for perm in generate_permutations(remaining):
        permutations.append([numbers[i]] + perm)

return permutations


def find_valid_orders(numbers):
    permutations = generate_permutations(numbers)
    valid_orders = []
for perm in permutations:
    if is_valid_order(perm):
        valid_orders.append(perm)

return valid_orders


numbers = list(range(1, 14))
valid_orders = find_valid_orders(numbers)
for order in valid_orders:
    print(order)