CODEWITHSUNDEEP
pythonmathcombinatorics
V.Petretto
V.Petretto

Reputation: 319

Python: How to calculate combinations of parts of a given number, giving the number, list lenght, first and last number

I'm very stuck on this (probably because I'm new to computer programming). I have the following code, from the question: [https://stackoverflow.com/questions/37616841/python-find-all-possible-combinations-of-parts-of-a-given-number/37617708?noredirect=1#comment62719215_37617708]

def sum_to_n(n, size, limit=None):
    """Produce all lists of `size` positive integers in decreasing order
    that add up to `n`."""
    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + size - 1) // size
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):
        for tail in sum_to_n(n - i, size - 1, i):
            yield [i] + tail

for partition in sum_to_n(8, 3):
    print (partition)

[6, 1, 1]
[5, 2, 1]
[4, 3, 1]
[4, 2, 2]
[3, 3, 2]

Is it very useful but I'm trying to modify it in order to set some options. Suppose I want to have only the results in which the first number of the list is 4 and the last of the list is 1. At the moment I use this solution:

def sum_to_n(n,first, last, size, limit=None):
    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + size - 1) // size
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):
        if i <=first:
            for tail in sum_to_n(n - i,first,last, size - 1, i):
                ll=len(tail)
                if tail[ll-1]==last:
                    yield [i] + tail

for i in sum_to_n(8,4,1,3):
    if i[0]==4 and i[size-1]==1:
        print(i)
    if i[0]>4:
        break

[4,3,1]

But with larger integers the program is doing a lot of unwanted work. For example, the for i in range(start, stop): computes all the possible first numbers of the list and not only the "first" parameter needed and the function does not work without it. Someone can suggest a better and faster solution to call the function giving the parameters needed in order to have only the requested computations?

Upvotes: 0

Views: 104

Answers (1)

Mikael Rousson
Mikael Rousson

Reputation: 2277

Since you know the first number, you just need to solve if for the last one.

In your example, that would give something like:

for res in sum_to_n(n=8-4, last=1, size=3-1):
   print([4] + res)

Upvotes: 1

Related Questions