Как создать комбинацию из двух чисел, равных заданному входу

Question

Я пытаюсь сгенерировать комбинацию из двух чисел, используя только 5 и 7, которые будут равны сумме любого данного ввода.Диапазон ввода составляет 24: 1000.До сих пор я определял, делится ли входное значение на 5 или 7, а затем генерирует список, сумма которого равна входному значению.
Вот мой рабочий пример:

def change(amount):
    if amount not in range(24,1001):
       print("The number is outside the range.")
    else:
       remainder=amount%5
    if remainder==0:
       n = int(amount/5)
       array=[0 for i in range(n)]
       for i in range(n):
       array[i]=5
       return array, sum(array)
    else:
       remainder=amount%7
    if remainder==0:
       n = int(amount/7)
       array=[0 for i in range(n)]
       for i in range(n):
       array[i]=7
       return array, sum(array)
    else: 
     # here is where am stuck       
print(change(28))

Требуется выводбыть в форме массива.Например: для change (24) массив должен быть [5,5,7,7].

Answer 1

Для этого вам не нужны циклы, просто немного алгебры.Подробности смотрите в комментариях.

def change(amount):
    if not 24 <= amount <= 1000:
       print("The number is outside the range.")
       return None

    # 5*3 - 7*2 = 1, so 5*(3*n) + 7*(-2*n) = n, and therefore
    # 5*(3*n - 7*k) + 7*(5*k - 2*n) = n for all k
    # We want to find a small k so that the terms in each bracket are positive
    k = 3 * amount // 7
    x = 3 * amount - 7 * k
    y = 5 * k - 2 * amount
    return x, y, [5] * x + [7] * y

# Print the sequences for some small amounts
for i in range(24, 70):
    x, y, seq = change(i)
    print(i, x, y, sum(seq) == i)

# Check all values in the range
for i in range(24, 1001):
    x, y, seq = change(i)
    assert sum(seq) == i
print('ok')

output

24 2 2 True
25 5 0 True
26 1 3 True
27 4 1 True
28 0 4 True
29 3 2 True
30 6 0 True
31 2 3 True
32 5 1 True
33 1 4 True
34 4 2 True
35 0 5 True
36 3 3 True
37 6 1 True
38 2 4 True
39 5 2 True
40 1 5 True
41 4 3 True
42 0 6 True
43 3 4 True
44 6 2 True
45 2 5 True
46 5 3 True
47 1 6 True
48 4 4 True
49 0 7 True
50 3 5 True
51 6 3 True
52 2 6 True
53 5 4 True
54 1 7 True
55 4 5 True
56 0 8 True
57 3 6 True
58 6 4 True
59 2 7 True
60 5 5 True
61 1 8 True
62 4 6 True
63 0 9 True
64 3 7 True
65 6 5 True
66 2 8 True
67 5 6 True
68 1 9 True
69 4 7 True
ok

Это не обязательно дает самую короткую последовательность для каждой суммы,но обычно он близок к оптимальному, и нетрудно изменить этот код, чтобы получить оптимальный.Но это останется в качестве упражнения для читателя.;)

Чтобы узнать больше об этой технике, см. Статью в Википедии о линейных Диофантовых уравнениях .

Answer 2

Это самый быстрый, что я мог придумать, поскольку он использует только один цикл while.

def change(amount):
    if not 24 <= amount <= 1001:
        print('{} is outside range'.format(amount))
        return
    sevens = []
    fives, remainder = divmod(amount, 5)
    while remainder:
        amount -= 7
        sevens.append(7)
        fives, remainder = divmod(amount, 5)
    return [5] * fives + sevens

PS: пожалуйста, не смешивайте размеры таблиц: -)

Answer 3

Для всех комбинаций здесь есть идея.Циклы можно оптимизировать дальше

import itertools


def change(target):
    nums = [5, 7]
    min_len = int(target / 7)
    max_len = int(target / 5) + 1

    res = []
    for len_ in range(min_len, max_len):
        r = itertools.combinations_with_replacement(nums, len_)
        for item in r:
            if sum(item) == target:
                res.append(item)

    return res

И немного оптимизировать.Соберите все комбинации в пределах возможного диапазона и отфильтруйте те с суммой == target.

import itertools


def change(target):
    nums = [5, 7]
    min_len = int(target / 7)
    max_len = int(target / 5) + 1

    res = []
    for len_ in range(min_len, max_len):
        res += (list(itertools.combinations_with_replacement(nums, len_)))

    return list(filter(lambda x: sum(x) == target, res))

Вывод, который содержит все возможные комбинации для цели = 70

[(7, 7, 7, 7, 7, 7, 7, 7, 7, 7), (5, 5, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7), (5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5)]

Без какой-либо петли в стиле FP.Сокращение всех возможных комбинаций в один список и фильтрация правильных элементов этого списка в ответ.

import itertools
from functools import reduce


def change(target):
    nums = [5, 7]
    min_len = int(target / 7)
    max_len = int(target / 5) + 1

    res = reduce(lambda x, y: 
                 x + (list(itertools.combinations_with_replacement(nums, y))),
                 range(min_len, max_len), [])


    return list(filter(lambda x: sum(x) == target, res))

Answer 4

Самый простой подход, который я мог придумать

def change(target):
    if target not in range(24,1001):
           raise ValueError("The number is outside the range.")
    res = []
    while target % 5 != 0:
        res.append(7)
        target -= 7

    while target != 0:
        res.append(5)
        target -= 5

    return res


change(28)
>>> [7, 7, 7, 7]