Welcome, guest | Sign In | My Account | Store | Cart

This is a generator that generates all tuples of n integers (>=0) with a given sum s. The generator can make the difference between tuples (3,0,0) and (0,3,0) or not (see order parameter).

Python, 32 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from itertools import permutations

def tuples_sum(nbval,total,order=True) :
    """ 
        Generate all the tuples L of nbval positive or nul integer 
        such that sum(L)=total.
        The tuples may be ordered (decreasing order) or not
    """
    if nbval == 0 and total == 0 : yield tuple() ; raise StopIteration
    if nbval == 1 : yield (total,) ; raise StopIteration
    if total==0 : yield (0,)*nbval ; raise StopIteration
    for start in range(total,0,-1) :
        for qu in tuples_sum(nbval-1,total-start) :
            if qu[0]<=start :
                sol=(start,)+qu
                if order : yield sol
                else :
                    l=set()
                    for p in permutations(sol,len(sol)) :
                        if p not in l :
                            l.add(p)
                            yield p
    
if __name__=='__main__' :
    print("How to obtain 5 by adding a+b+c (>=0) ? ")
    print("Give me the list of (a,b,c) tuples.")
    g=tuples_sum(3,5,order=False)
    print(list(g))
    
    print("How to obtain 6 by adding 3 positive or nul integers ?")
    g=tuples_sum(3,6,order=True)
    print(list(g))

If you run the module, you will get :

 How to obtain 5 by adding a+b+c (>=0) ? 
 Give me the list of (a,b,c) tuples.
 [(5, 0, 0), (0, 5, 0), (0, 0, 5), (4, 1, 0), (4, 0, 1), (1, 4, 0), (1, 0, 4), (0, 4, 1), 
 (0, 1, 4), (3, 2, 0), (3, 0, 2), (2, 3, 0), (2, 0, 3), (0, 3, 2), (0, 2, 3), (3, 1, 1), 
 (1, 3, 1), (1, 1, 3), (2, 2, 1), (2, 1, 2), (1, 2, 2)] 
 How to obtain 6 by adding 3 positive or nul integers ?
 [(6, 0, 0), (5, 1, 0), (4, 2, 0), (4, 1, 1), (3, 3, 0), (3, 2, 1), (2, 2, 2)]
Created by SnarkTurne on Tue, 16 Jul 2013 (MIT)
Python recipes (4591)
SnarkTurne's recipes (2)

Required Modules

Other Information and Tasks