I'm learning python and I have a problem with this task

I have a list of numbers 0<=n<=(end), and I want to find all combinations of lists with 6 elements whose elements sum up to a certain number S

I'll use the list created by the function to check some conditions which I think would be another kind of task. Right now, I'm looking for an effective way to do the task above! I tried to use Brute-force, but I guess the time complexity gets exponential!

Pseudocode or suggestion of a known algorithm would also be nice for me! I just a piece of advice, thank you.

For example,

def f(end, S):
   #definition of the function

input f(14, 14)
output [14, 0, 0, 0, 0, 0] [0, 14, 0, 0, 0, 0] ...(and so on)... [0, 0, 3, 0, 7, 4] [0, 0, 3, 0, 6, 5] (and so on)...

Below is information about the condition I mentioned above, still my main question is about the task above! So you can just ignore the below part

I have three different functions that return a String(the only possible outputs are A, B, C or (none). eg) f1(list) --> 'A' f2(list) --> 'B' f3(list) --> 'C'

I will put the list created by the function I asked for into those functions and find out which cases of lists lead the three functions to return a String different from each other, while they all do not return (none)(f1, f2, f3 should return A or B or C). I will make a loop for each list and find out which of them meets this condition.

CodePudding user response：

Python has an extensive standard library which is pretty fast and useful. In this case, itertools' combinations_with_replacement does the trick.

You just need to pick the combinations that sum up to N

For example, this code

import itertools as it

N = 14
SIZE = 6

lst = range(N 1)
sum_n_combs = [
    comb for comb in it.combinations_with_replacement(lst, SIZE)
    if sum(comb) == N
]
print(sum_n_combs)

produces

[(0, 0, 0, 0, 0, 14), (0, 0, 0, 0, 1, 13), (0, 0, 0, 0, 2, 12), (0, 0, 0, 0, 3, 11), (0, 0, 0, 0, 4, 10), (0, 0, 0, 0, 5, 9), (0, 0, 0, 0, 6, 8), (0, 0, 0, 0, 7, 7), (0, 0, 0, 1, 1, 12), (0, 0, 0, 1, 2, 11), (0, 0, 0, 1, 3, 10), (0, 0, 0, 1, 4, 9), (0, 0, 0, 1, 5, 8), (0, 0, 0, 1, 6, 7), (0, 0, 0, 2, 2, 10), (0, 0, 0, 2, 3, 9), (0, 0, 0, 2, 4, 8), (0, 0, 0, 2, 5, 7), (0, 0, 0, 2, 6, 6), (0, 0, 0, 3, 3, 8), (0, 0, 0, 3, 4, 7), (0, 0, 0, 3, 5, 6), (0, 0, 0, 4, 4, 6), (0, 0, 0, 4, 5, 5), (0, 0, 1, 1, 1, 11), (0, 0, 1, 1, 2, 10), (0, 0, 1, 1, 3, 9), (0, 0, 1, 1, 4, 8), (0, 0, 1, 1, 5, 7), (0, 0, 1, 1, 6, 6), (0, 0, 1, 2, 2, 9), (0, 0, 1, 2, 3, 8), (0, 0, 1, 2, 4, 7), (0, 0, 1, 2, 5, 6), (0, 0, 1, 3, 3, 7), (0, 0, 1, 3, 4, 6), (0, 0, 1, 3, 5, 5), (0, 0, 1, 4, 4, 5), (0, 0, 2, 2, 2, 8), (0, 0, 2, 2, 3, 7), (0, 0, 2, 2, 4, 6), (0, 0, 2, 2, 5, 5), (0, 0, 2, 3, 3, 6), (0, 0, 2, 3, 4, 5), (0, 0, 2, 4, 4, 4), (0, 0, 3, 3, 3, 5), (0, 0, 3, 3, 4, 4), (0, 1, 1, 1, 1, 10), (0, 1, 1, 1, 2, 9), (0, 1, 1, 1, 3, 8), (0, 1, 1, 1, 4, 7), (0, 1, 1, 1, 5, 6), (0, 1, 1, 2, 2, 8), (0, 1, 1, 2, 3, 7), (0, 1, 1, 2, 4, 6), (0, 1, 1, 2, 5, 5), (0, 1, 1, 3, 3, 6), (0, 1, 1, 3, 4, 5), (0, 1, 1, 4, 4, 4), (0, 1, 2, 2, 2, 7), (0, 1, 2, 2, 3, 6), (0, 1, 2, 2, 4, 5), (0, 1, 2, 3, 3, 5), (0, 1, 2, 3, 4, 4), (0, 1, 3, 3, 3, 4), (0, 2, 2, 2, 2, 6), (0, 2, 2, 2, 3, 5), (0, 2, 2, 2, 4, 4), (0, 2, 2, 3, 3, 4), (0, 2, 3, 3, 3, 3), (1, 1, 1, 1, 1, 9), (1, 1, 1, 1, 2, 8), (1, 1, 1, 1, 3, 7), (1, 1, 1, 1, 4, 6), (1, 1, 1, 1, 5, 5), (1, 1, 1, 2, 2, 7), (1, 1, 1, 2, 3, 6), (1, 1, 1, 2, 4, 5), (1, 1, 1, 3, 3, 5), (1, 1, 1, 3, 4, 4), (1, 1, 2, 2, 2, 6), (1, 1, 2, 2, 3, 5), (1, 1, 2, 2, 4, 4), (1, 1, 2, 3, 3, 4), (1, 1, 3, 3, 3, 3), (1, 2, 2, 2, 2, 5), (1, 2, 2, 2, 3, 4), (1, 2, 2, 3, 3, 3), (2, 2, 2, 2, 2, 4), (2, 2, 2, 2, 3, 3)]

CodePudding user response：

You can do -

def f(Num, List):
    n = Num 
    l = List 
    for i in range(len(List)):
        if len(List) > 0 and len(List) != 1:
            x= List.pop(0)
            y= List.pop(0)
            if x   y == Num:
                print(str(x)   " and "   str(y)   " are a sum of "   str(Num))  
        else:
            # print("the list has no more values")
            exit(0)

f(10, [5, 5, 8, 2, 3, 4, 3]) # 3, 4, 3 will not be checked

the reason why 3,4,3 will not be checked is because the program does not support the sums of more then 2 numbers, imagine if you give this list [4, 4, 2] and want to find 10 as its sum, the program will not do anything and just quit, because it does not support 3 or more numbers.