An interesting problem

[Redturtle098]

Hey everyone,
 

So as you already know, I have a bit of a tricky problem to solve. I need to create a python program that takes an integer input (For example, 3), and then churns out all possible combinations to make that number (For example: 1,1,1;  1,2;  2,1;  0,3)
In addition to that, it should avoid any previously calculated solutions, so in this example, it should only print out 1,1,1 once.

 

It should be something like this:

 

Input: 3

1,1,1

2,1

1,2

0,3

3,0

End

I have no idea where to start, and I'm only a beginner, so I'd like to avoid using any modules.

Any help with this would be awesome
Thanks!!

[tikker]

Are we talking positive integers only? The brute force way would be to loop over numbers while subtracting and then constantly checking if you can reach 0 that way.

You can cheat the first solution since you can always create that number by adding ones, so that's the easy one. If you consider a+b and b+a to be the same thing, this can limit the amount of numbers you need to search as well.

[Redturtle098]

1 hour ago, tikker said:

Are we talking positive integers only? The brute force way would be to loop over numbers while subtracting and then constantly checking if you can reach 0 that way.

You can cheat the first solution since you can always create that number by adding ones, so that's the easy one. If you consider a+b and b+a to be the same thing, this can limit the amount of numbers you need to search as well.

Yeah, I'm trying for positive integers first, because it's easier to calculate in my head
I was going to loop it, but I'm unsure on the algorithm that would be used to accomplish this. Do you have an example of the loop you suggested?
And yeah, a+b and b+a are the same, but it'd definitely be useful to have all the numbers!!!
Thanks again for your help!!

[KNG_HOLDY]

i dont know if this is what u wanted but w/e i was bored
 

Code:

Spoiler

 

import itertools

def getPermutations(number):
    interval = [x for x in range(number+1)] 
    permutations = list(itertools.product(interval, repeat=number))
    return permutations  

def crunch(number):    
    permutations = getPermutations(number)
    result = []
    for permutation in permutations:
        _sum = sum(permutation)
        if(_sum == number):
            result.append(permutation)
    return result

 

 

 

 

Example input 3

Spoiler

Input: 3
Result:
[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

 

Example Input 5

Spoiler

Input: 5
Result:
[(0, 0, 0, 0, 5), (0, 0, 0, 1, 4), (0, 0, 0, 2, 3), (0, 0, 0, 3, 2), (0, 0, 0, 4, 1), (0, 0, 0, 5, 0), (0, 0, 1, 0, 4), (0, 0, 1, 1, 3), (0, 0, 1, 2, 2), (0, 0, 1, 3, 1), (0, 0, 1, 4, 0), (0, 0, 2, 0, 3), (0, 0, 2, 1, 2), (0, 0, 2, 2, 1), (0, 0, 2, 3, 0), (0, 0, 3, 0, 2), (0, 0, 3, 1, 1), (0, 0, 3, 2, 0), (0, 0, 4, 0, 1), (0, 0, 4, 1, 0), (0, 0, 5, 0, 0), (0, 1, 0, 0, 4), (0, 1, 0, 1, 3), (0, 1, 0, 2, 2), (0, 1, 0, 3, 1), (0, 1, 0, 4, 0), (0, 1, 1, 0, 3), (0, 1, 1, 1, 2), (0, 1, 1, 2, 1), (0, 1, 1, 3, 0), (0, 1, 2, 0, 2), (0, 1, 2, 1, 1), (0, 1, 2, 2, 0), (0, 1, 3, 0, 1), (0, 1, 3, 1, 0), (0, 1, 4, 0, 0), (0, 2, 0, 0, 3), (0, 2, 0, 1, 2), (0, 2, 0, 2, 1), (0, 2, 0, 3, 0), (0, 2, 1, 0, 2), (0, 2, 1, 1, 1), (0, 2, 1, 2, 0), (0, 2, 2, 0, 1), (0, 2, 2, 1, 0), (0, 2, 3, 0, 0), (0, 3, 0, 0, 2), (0, 3, 0, 1, 1), (0, 3, 0, 2, 0), (0, 3, 1, 0, 1), (0, 3, 1, 1, 0), (0, 3, 2, 0, 0), (0, 4, 0, 0, 1), (0, 4, 0, 1, 0), (0, 4, 1, 0, 0), (0, 5, 0, 0, 0), (1, 0, 0, 0, 4), (1, 0, 0, 1, 3), (1, 0, 0, 2, 2), (1, 0, 0, 3, 1), (1, 0, 0, 4, 0), (1, 0, 1, 0, 3), (1, 0, 1, 1, 2), (1, 0, 1, 2, 1), (1, 0, 1, 3, 0), (1, 0, 2, 0, 2), (1, 0, 2, 1, 1), (1, 0, 2, 2, 0), (1, 0, 3, 0, 1), (1, 0, 3, 1, 0), (1, 0, 4, 0, 0), (1, 1, 0, 0, 3), (1, 1, 0, 1, 2), (1, 1, 0, 2, 1), (1, 1, 0, 3, 0), (1, 1, 1, 0, 2), (1, 1, 1, 1, 1), (1, 1, 1, 2, 0), (1, 1, 2, 0, 1), (1, 1, 2, 1, 0), (1, 1, 3, 0, 0), (1, 2, 0, 0, 2), (1, 2, 0, 1, 1), (1, 2, 0, 2, 0), (1, 2, 1, 0, 1), (1, 2, 1, 1, 0), (1, 2, 2, 0, 0), (1, 3, 0, 0, 1), (1, 3, 0, 1, 0), (1, 3, 1, 0, 0), (1, 4, 0, 0, 0), (2, 0, 0, 0, 3), (2, 0, 0, 1, 2), (2, 0, 0, 2, 1), (2, 0, 0, 3, 0), (2, 0, 1, 0, 2), (2, 0, 1, 1, 1), (2, 0, 1, 2, 0), (2, 0, 2, 0, 1), (2, 0, 2, 1, 0), (2, 0, 3, 0, 0), (2, 1, 0, 0, 2), (2, 1, 0, 1, 1), (2, 1, 0, 2, 0), (2, 1, 1, 0, 1), (2, 1, 1, 1, 0), (2, 1, 2, 0, 0), (2, 2, 0, 0, 1), (2, 2, 0, 1, 0), (2, 2, 1, 0, 0), (2, 3, 0, 0, 0), (3, 0, 0, 0, 2), (3, 0, 0, 1, 1), (3, 0, 0, 2, 0), (3, 0, 1, 0, 1), (3, 0, 1, 1, 0), (3, 0, 2, 0, 0), (3, 1, 0, 0, 1), (3, 1, 0, 1, 0), (3, 1, 1, 0, 0), (3, 2, 0, 0, 0), (4, 0, 0, 0, 1), (4, 0, 0, 1, 0), (4, 0, 1, 0, 0), (4, 1, 0, 0, 0), (5, 0, 0, 0, 0)]

 

 

 

//Edit 

this solution returns every possible perumtation 

for example (0, 1) (1, 0) are both present in the result of input 1 even tho they are the same

[Guest]

You’ll need find kind of recursion or loop. 

Recursion is basically doing the same thing over and over. If used properly, it will eventually leave the recursive state. 

 

As for the math I think that’s what the professor wants you to figure out. 

[wasab]

Just brute force all the possible permutations.

[vorticalbox]

On 28/04/2018 at 11:59 AM, KNG_HOLDY said:

i dont know if this is what u wanted but w/e i was bored
 

Code:

  Reveal hidden contents

 

import itertools

def getPermutations(number):
    interval = [x for x in range(number+1)] 
    permutations = list(itertools.product(interval, repeat=number))
    return permutations  

def crunch(number):    
    permutations = getPermutations(number)
    result = []
    for permutation in permutations:
        _sum = sum(permutation)
        if(_sum == number):
            result.append(permutation)
    return result

 

 

 

 

Example input 3

  Reveal hidden contents

Input: 3
Result:
[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

 

Example Input 5

  Reveal hidden contents

Input: 5
Result:
[(0, 0, 0, 0, 5), (0, 0, 0, 1, 4), (0, 0, 0, 2, 3), (0, 0, 0, 3, 2), (0, 0, 0, 4, 1), (0, 0, 0, 5, 0), (0, 0, 1, 0, 4), (0, 0, 1, 1, 3), (0, 0, 1, 2, 2), (0, 0, 1, 3, 1), (0, 0, 1, 4, 0), (0, 0, 2, 0, 3), (0, 0, 2, 1, 2), (0, 0, 2, 2, 1), (0, 0, 2, 3, 0), (0, 0, 3, 0, 2), (0, 0, 3, 1, 1), (0, 0, 3, 2, 0), (0, 0, 4, 0, 1), (0, 0, 4, 1, 0), (0, 0, 5, 0, 0), (0, 1, 0, 0, 4), (0, 1, 0, 1, 3), (0, 1, 0, 2, 2), (0, 1, 0, 3, 1), (0, 1, 0, 4, 0), (0, 1, 1, 0, 3), (0, 1, 1, 1, 2), (0, 1, 1, 2, 1), (0, 1, 1, 3, 0), (0, 1, 2, 0, 2), (0, 1, 2, 1, 1), (0, 1, 2, 2, 0), (0, 1, 3, 0, 1), (0, 1, 3, 1, 0), (0, 1, 4, 0, 0), (0, 2, 0, 0, 3), (0, 2, 0, 1, 2), (0, 2, 0, 2, 1), (0, 2, 0, 3, 0), (0, 2, 1, 0, 2), (0, 2, 1, 1, 1), (0, 2, 1, 2, 0), (0, 2, 2, 0, 1), (0, 2, 2, 1, 0), (0, 2, 3, 0, 0), (0, 3, 0, 0, 2), (0, 3, 0, 1, 1), (0, 3, 0, 2, 0), (0, 3, 1, 0, 1), (0, 3, 1, 1, 0), (0, 3, 2, 0, 0), (0, 4, 0, 0, 1), (0, 4, 0, 1, 0), (0, 4, 1, 0, 0), (0, 5, 0, 0, 0), (1, 0, 0, 0, 4), (1, 0, 0, 1, 3), (1, 0, 0, 2, 2), (1, 0, 0, 3, 1), (1, 0, 0, 4, 0), (1, 0, 1, 0, 3), (1, 0, 1, 1, 2), (1, 0, 1, 2, 1), (1, 0, 1, 3, 0), (1, 0, 2, 0, 2), (1, 0, 2, 1, 1), (1, 0, 2, 2, 0), (1, 0, 3, 0, 1), (1, 0, 3, 1, 0), (1, 0, 4, 0, 0), (1, 1, 0, 0, 3), (1, 1, 0, 1, 2), (1, 1, 0, 2, 1), (1, 1, 0, 3, 0), (1, 1, 1, 0, 2), (1, 1, 1, 1, 1), (1, 1, 1, 2, 0), (1, 1, 2, 0, 1), (1, 1, 2, 1, 0), (1, 1, 3, 0, 0), (1, 2, 0, 0, 2), (1, 2, 0, 1, 1), (1, 2, 0, 2, 0), (1, 2, 1, 0, 1), (1, 2, 1, 1, 0), (1, 2, 2, 0, 0), (1, 3, 0, 0, 1), (1, 3, 0, 1, 0), (1, 3, 1, 0, 0), (1, 4, 0, 0, 0), (2, 0, 0, 0, 3), (2, 0, 0, 1, 2), (2, 0, 0, 2, 1), (2, 0, 0, 3, 0), (2, 0, 1, 0, 2), (2, 0, 1, 1, 1), (2, 0, 1, 2, 0), (2, 0, 2, 0, 1), (2, 0, 2, 1, 0), (2, 0, 3, 0, 0), (2, 1, 0, 0, 2), (2, 1, 0, 1, 1), (2, 1, 0, 2, 0), (2, 1, 1, 0, 1), (2, 1, 1, 1, 0), (2, 1, 2, 0, 0), (2, 2, 0, 0, 1), (2, 2, 0, 1, 0), (2, 2, 1, 0, 0), (2, 3, 0, 0, 0), (3, 0, 0, 0, 2), (3, 0, 0, 1, 1), (3, 0, 0, 2, 0), (3, 0, 1, 0, 1), (3, 0, 1, 1, 0), (3, 0, 2, 0, 0), (3, 1, 0, 0, 1), (3, 1, 0, 1, 0), (3, 1, 1, 0, 0), (3, 2, 0, 0, 0), (4, 0, 0, 0, 1), (4, 0, 0, 1, 0), (4, 0, 1, 0, 0), (4, 1, 0, 0, 0), (5, 0, 0, 0, 0)]

 

 

 

//Edit 

this solution returns every possible perumtation 

for example (0, 1) (1, 0) are both present in the result of input 1 even tho they are the same

Without using external tools I would take the input (3) make the highest number you can get for that input length (999)

 

Then loop the range and add up each number (120 1+2+0) if that equals the input then push the result to a list.

 

Any 1/2 length valid you can just append the 0. E.g 12 you would just make it 012.

 

 

[Dash Lambda]

I'm a little late, but this is my solution:

 

What you're trying to find are compositions, where you represent a number as a sum of strictly positive integers. For an integer n, you can start with the composition consisting of n 1's and separate them with a choice of either a plus or a comma, and say a comma is 0 and a plus is 1. You get an n-1 bit binary number, and you just count up.

 

For example:

 

Input 3, get (1 _ 1 _ 1)

00: (1, 1, 1)

01: (1, 1 + 1) = (1, 2)

10: (1 + 1, 1) = (2, 1)

11: (1 + 1 + 1) = (3)

[jincio]

i think this should work if i get your question

 

Code:

Spoiler

target_num = 5
#the counter is used to keep track of the current sum value
#while step is the value of the element we are evaluate to insert in the combination
def sumComb(step, counter, v):
    if counter > target_num or step > target_num:
        return
    if counter == target_num:
        # if counter as reached the target_num print the list
        print(v)
        return
    else:
        # else append the step size to list
        v.append(step)
        # increment the counter by step and recurse
        sumComb(step, counter + step, v)
        # remove the last step item from list
        v.pop()
        # increment the step size and recurse
        sumComb(step + 1, counter, v)
sumComb( 1, 0, [])

 

[Redturtle098]

Thanks again for the help and information - I really do appreciate it!
Have a nice rest of the day everyone!!

[bowrilla]

I rather think it's not really solvable unless you specify what mathematical operations are allowed and how deep you want to go.l otherwise there are basically infinitely many possibilities for each number and you will run out of memory (at the same time having issues with variable length) not to mention the lack of computational power.

 

P.S.: this is pretty much related to cryptography and factorisation. The bigger your number the harder it gets and at some point even the super computers of NSA, CIA and so on aren't capable of solving those problems on a reasonable amount of time.

[Dash Lambda]

On 5/18/2018 at 11:07 AM, bowrilla said:

-snip-

You should read the thread. All the computer has to do is count.

[Meic]

def get_parts(n):
    parts = {(n,)}
    for i in range(1,n):
        for sub_parts in get_parts(n-i):
            parts.add(tuple(sorted((i,)+sub_parts)))
    return parts

get_parts(5)
{(1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 4), (2, 3), (5,)}

This solution is for a de-duped set of all combinations that sum to the initial value (just get all permutations of each group to answer the OP)

[bowrilla]

2 hours ago, Dash Lambda said:

You should read the thread. All the computer has to do is count.

That's not specifically stated? What about multiplication? What about substraction? What about division? How large is a factor allowed to become? What happens if we enter large integers (think of 64 bit unsigned integers)? There'd be trillions of possibilities even without accounting for substraction and factors larger than the initial integer. The problem as stated in the original post is too vague in order to find a working algorithm that can handle the task in reasonable time.

[vorticalbox]

On 23/05/2018 at 3:31 PM, bowrilla said:

That's not specifically stated? What about multiplication? What about substraction? What about division? How large is a factor allowed to become? What happens if we enter large integers (think of 64 bit unsigned integers)? There'd be trillions of possibilities even without accounting for substraction and factors larger than the initial integer. The problem as stated in the original post is too vague in order to find a working algorithm that can handle the task in reasonable time.

How very stackover flow of you....

 

The ops example of output is more than enough to conclude addition is what is required and that, when an example input of 3, is not trying to calculate massive numbers in which case you would probally calculate in ranges and across multiple processes.

[bowrilla]

5 hours ago, vorticalbox said:

How very stackover flow of you....

 

The ops example of output is more than enough to conclude addition is what is required and that, when an example input of 3, is not trying to calculate massive numbers in which case you would probally calculate in ranges and across multiple processes.

Then just look at the example itself: the possible 0 opens up an infinite amount of possibilities. Just add another 0 and you have a new solution. So even the example isn't precise enough and the op explicitly said "churns out all possible combinations to make that number". This is exactly why programs crash: programers who haven't given their algorithms enough thought. Even the given example has therefore infinitely many solutions by just adding more and more 0 since {3, 0} and {0, 3} are different solutions. 

[geo3]

2 hours ago, bowrilla said:

Then just look at the example itself: the possible 0 opens up an infinite amount of possibilities. Just add another 0 and you have a new solution. So even the example isn't precise enough and the op explicitly said "churns out all possible combinations to make that number". This is exactly why programs crash: programers who haven't given their algorithms enough thought. Even the given example has therefore infinitely many solutions by just adding more and more 0 since {3, 0} and {0, 3} are different solutions. 

Jesus dude, quit being pedantic. It's obvious what the OP is looking for.

[Dash Lambda]

On 5/25/2018 at 9:06 AM, bowrilla said:

-snip-

Compositions with 0 are called 'weak' compositions, and they're not generally considered when talking about compositions. They aren't computationally intensive at all, they can just be made arbitrarily long without changing their underlying structure.

 

Part of helping people with their questions is filling in the holes and/or inconsistencies. If what they're asking for doesn't work, but they're obviously trying to get at something that does, then you show them what works.

[Unimportant]

3 hours ago, Erik Sieghart said:

If you're going to be pedantic, I can be pedantic right back. An integer (32 bit) in programmer parlance is a value between -2,147,483,647  and 2,147,483,647.

To keep the pedantry alive: −2,147,483,648 and 2,147,483,647