Fastest way for the computer to find combinations of non-negative integers x_1<=x_2<=...<= x_n and sum to 100

Question

I want to find an efficient way for computer to handle LARGE NUMBER OF VARIABLES (say 50: x1, ... , x50) that do something like this: find ALL combinations [x1,x2,x3] satisfying:

1. 0 <= x1 <= x2 <= x3

2. x1 + x2 + x3 = 100

Here is an example of finding all combinations with sum = 100 but [1,99] and [99,1] are considered to be different here:

x=[]
for i, j in itertools.product(range(0,101), range(0,101)):
    if i+j==100:
       x.append([i,j])

I want to find a way to reduce the number of loops and give only things like:

[0,100], [1,99], [2,98], .........., [50,50]

And nothing from [51,49].

The main goal is doing this with 50 variables (x_1,...x_50) which sums up to 100.

It is not likely to do it with normal loop

Answer 1

For 3 variables of form i+j+k==100 we need two for loops and for n variables we need n-1 for loops to produce the result

for i in range(0,101):
    for j in range(i,101):
        if(100-j-i>=j):
            print i,j,100-j-i

Result

0 0 100
0 1 99
0 2 98
0 3 97
0 4 96
0 5 95
......
......
32 33 35
32 34 34
33 33 34

Edit 1

or if you dont want to write the code for n-1 loops use this recurisive function and it will be faster as i did some optimization to reduce its runtime

def foo(numberofvariables,sumofvar):
    templist=[0]*(numberofvariables)

    def fun(depthofrecursion,tempsum,sumofvar,var):

        if(depthofrecursion<numberofvariables-1):
            for i in range(var,(sumofvar/(numberofvariables-depthofrecursion)+2)):

                templist[depthofrecursion]=i;
                fun(depthofrecursion+1,tempsum+i,sumofvar,i)
        else:

            if(sumofvar-tempsum>=var):
                templist[numberofvariables-1]=sumofvar-tempsum
                for i in range(0,numberofvariables):
                    print templist[i],

                print 

    fun(0,0,sumofvar,0)

foo(3,100)

here the n is 3 (number of variables)and sum is 100 produces the same output as above

Answer 2

what about combinaison ??

import random
from itertools import combinations
l = random.sample(range(1, 10000), 100)

alist =[(x1,x2,x3) if  (0 <= x1 <= x2 <= x3 and sum([x1,x2,x3]) == 100) else None for x1,x2,x3 in combinations(sorted(l), 3)]
L = list(filter(None, alist))

output

[(1, 4, 95),
 (1, 7, 92),
 (1, 10, 89),
 (1, 12, 87),
 (1, 17, 82),
 (1, 18, 81),
 (1, 30, 69),
 (1, 32, 67),
 (1, 34, 65),
 (1, 38, 61),
 (1, 49, 50),
 (2, 3, 95),
 (2, 5, 93),
 (2, 7, 91),
 (2, 10, 88),
 (2, 12, 86),
 (2, 17, 81),
 (2, 18, 80),
 (2, 22, 76),
 (2, 30, 68),
 (2, 33, 65),
 (3, 4, 93),
 (3, 5, 92),
 (3, 7, 90),
 (3, 10, 87),
 (3, 12, 85),
 (3, 17, 80),