Как сгенерировать 5 неповторяющихся чисел дающих в сумме 100?

Question

Хочу реализовать генерацию 5 чисел от 0 до 100, в сумме эти числа = 100, не должно быть повторений и должны быть использованы все варианты перебора.

Мой код:

for a in range(101):
    for b in range(101):
        for c in range(101):
            for d in range(101):
                for e in range(101):
                    if a + b + c + d + e == 100:
                       print(a, b, c, d, e)

Answer 1

Раз вам нужны все комбинации, то ваш способ, если его немного модифицировать так, чтобы плохие комбинации не генерировались вообще, будет самым быстрым. Однако "очень долго" - это естественно, число вариантов для суммы 100 довольно велико.

n = 6
for a in range(n+1):
    for b in range(n-a+1):
        for c in range(n-a-b+1):
            for d in range(n-a-b-c + 1):
                e = n-a-b-c-d
                print(a, b, c, d, e)

Или с запоминанием, чтобы сократить вычисления:

n = 6
for a in range(n+1):
    sa = n - a
    for b in range(sa+1):
        sb = sa - b
        for c in range(sb+1):
            sc = sb - c
            for d in range(sc + 1):
                e = sc - d
                print(a, b, c, d, e)

Answer 2

def combinations(t, n):

    board = [0] * n
    
    def search(k, s):
        if k == n - 1:
            board[k] = s
            yield board
            return
        for v in range(t - s + 1):
            board[k] = v
            yield from search(k + 1, s + v)

    return map(tuple, search(0, 0))


for a, b, c, d, e in combinations(100, 5):
    print(a, b, c, d, e)

$ time python combinations.py | wc -l
4598126

real  0m10.356s
user  0m10.348s
sys   0m0.096s

Число комбинаций не такое огромное. Если n - количество слагаемых, t - сумма комбинации, то число комбинаций будет равно Cnk(t + n - 1, n - 1). Проверка:

$ python
Python 3.10.0 (default, Oct 16 2021, 12:17:56) [GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
@>>> import math
@>>> t = 100
@>>> n = 5
@>>> math.comb(t + n - 1, n - 1)
4598126

Answer 3

import itertools

all_combinations = itertools.combinations(range(100), 5)
valid_combinations = [combo for combo in all_combinations if sum(combo) == 100]
print(valid_combinations)

БЛОГ НА HUSL

Как сгенерировать 5 неповторяющихся чисел дающих в сумме 100?

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