-1

This seems like a repost but it's not. Most people asked for the pair numbers. I need all numbers, not just two. Like n0+n1+n2+n3+n4+...+n100=x And also, each number must be lower than the number comes before him. For example for 8 output must be:

There are 5:
7+1
5+3
6+2
5+2+1
4+3+1

In here you can see 5>3 and 6>2 and vice versa. I came so close with this code. I found this on stackoverflow, and then improved it to according to my needs. However I tested it on a super computer, that if you give 200 to this, it says it's wrong. I just don't get it how could this be wrong? Please can someone help me improve this? With my pc it takes a lot of time. Give this 50, and it will still take hours. Here is my code:

from itertools import combinations
def solution(N):
    array=[]
    counter=0
    for i in range(N):
        if(i==0):
            continue
        array.append(i)
    for K in range(N):
        for comb in combinations(array, K):
            if sum(comb) == N:
                counter+=1
                #print(comb) uncomment this if you like, it prints pairs.
    return counter  

res=solution(50)
print(res)

By the way, can I do it without itertools at all? Maybe it causes problems.

crag hack
  • 51
  • 7
  • 1
    Your algo is highly inperformant. (For 50) You create all combinations from 1 up to 50 numbers out of [1,2,3,4,...,49] and throw away all that do not sum up to 50 - most of the stuff you generate is garbage and just takes time. If 49 is in your choosen numbers only one 1 will fit - neither of 2..48 will do nor will any of the combinations that use more then 2 numbers. Rethink what you need to do and only generate what is needed. You might want to look into using [memoization](https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python) – Patrick Artner Nov 05 '21 at 12:46
  • Without checking the validity of your algorithm, it's likely that it is correct, but so inefficient that it times out during the tests and hence fails. – Reti43 Nov 05 '21 at 13:42

2 Answers2

1

I think I may have found a solution, I will share it and maybe you can check with me if it is correct :) I assumed that all numbers must be smaller than N.

To start, I am not so sure your code is necessarily wrong. I think it produces the right answers but maybe you should consider what is happening and why your code takes so long. Currently, you are checking for all combination of sums, but by iterating in another way you can exclude many possibilities. For example, suppose my goal is to find all sums that result in a total of 8. Suppose I now have a sum of 6 + 5 = 11. Currently, you are still checking all other possibilities when adding other numbers (i.e. 6 + 5 + 4 and 6 + 5 + 3 etc etc), but we already know they all will be >8, hence we do not even have to compute them.

As a solution we can start with the highest number smaller than our goal, i.e. 7 in our example. Then we will try all combinations with numbers smaller than this. As soon as our sum gets bigger than 8, we do not follow the trail further. This sounds a lot like recursing, which is how I currently implemented it.

To get an idea (I hope it is correct, I haven't tested it extensively):

def solution(goal, total_solutions=0, current_sum=0.0, current_value=None):
    if current_value is None:
        current_value = goal

    # Base condition
    if current_sum >= goal:
        if current_sum == goal:
            return total_solutions + 1
        return total_solutions

    for new_value in range(current_value - 1, 0, -1):
        total_solutions = solution(
            goal, total_solutions, current_sum + new_value, new_value
        )
    return total_solutions


res = solution(8)
print(res)  # prints 5

So as an answer to your question, yes you can do it with itertools, but it will take a long time because you will be checking a lot of sums of which you do not really need to check.

I compared this program with yours and it produces the same output up until N=30. But then your code really starts to blow up so I won't check further.

swopper
  • 51
  • 4
  • Thank you, this seems better but however, if you want 200, it's still returning wrong number. Result must be around 480 million. – crag hack Nov 05 '21 at 13:08
  • Can you maybe inspect from where the code does not give the correct answer? For example for 8 we both get the right answer but from which number does it yield the wrong answer? Otherwise it might help to give a precise definition of the problem you're trying to solve! – swopper Nov 05 '21 at 13:10
  • It's actually a google foobar challenge, I simplified it to this. And no I can't test it, there is no such thing. It's against the rules. Search this: the grandest staircase of them all foobar. You'll see the problem. – crag hack Nov 05 '21 at 13:32
  • In that case you might want to check this post: https://stackoverflow.com/questions/52654530/programming-challenge-how-does-this-algorithm-tied-to-number-theory-work – swopper Nov 05 '21 at 13:38
  • It only gives me the answer of 5 and 200. For 200 I can't even test the result because it would take hours and hours. Only on their server I can test. – crag hack Nov 05 '21 at 13:41
1

The Answer you're looking for is in the post : programming challenge: how does this algorithm (tied to Number Theory) work?

The classical method start taking some time at the 100th step but the use of memoization also called dynamic programming reduces the complexity drastically and allows your algorithm to compute at the 4000th step without taking any time at all.

Julien Cardinal
  • 21
  • 3