Generating permutation in Python with specific rule

Question

Let say a=[A, B, C, D], each element has a weight w, and is set to 1 if selected, 0 if otherwise. I'd like to generate permutation in the below order

1,1,1,1
1,1,1,0
1,1,0,1
1,1,0,0
1,0,1,1
1,0,1,0
1,0,0,1
1,0,0,0

0,1,1,1
0,1,1,0
0,1,0,1
0,1,0,0
0,0,1,1
0,0,1,0
0,0,0,1
0,0,0,0

Let's w=[1,2,3,4] for item A,B,C,D ... and max_weight = 4. For each permutation, if the accum weight has exceeded max_weight, stop calculation for that permutation, move to next permutation. For eg.

1,1,1    --> 6 > 4, exceeded, stop, move to next
1,1,1    --> 6 > 4, exceeded, stop, move to next  
1,1,0,1  --> 7 > 4  finished, move to next  
1,1,0,0  --> 3      finished, move to next  
1,0,1,1  --> 8 > 4, finished, move to next
1,0,1,0  --> 4      finished, move to next  
1,0,0,1  --> 5 > 4  finished, move to next  
1,0,0,0  --> 1      finished, move to next  
etc calculation continue

So far, [1,0,1,0] is the best combination which does not exceeded max_weight 4

My questions are

1. What's the algorithm which generate the required permutation? Or any suggestion I could generate the permutation?
2. As the number of element can be up to 10000, and the calculation stop if the accum weight for the branch exceeds max_weight, it is not necessary to generate all permutation first before the calculation. How can the algo in (1) generate permutation on the fly?

Answer 1

Use itertools.product function to generate permutation.

from itertools import *

w = [1,2,3,4]
max_weight = 4
for selection in product([1,0], repeat=len(w)):
    accum = sum(compress(w, selection))
    if accum > 4:
        print '{}  --> {} > {}, exceeded, stop, move to next'.format(selection, accum, max_weight)
    else:
        print '{}  --> {}    , finished, move to next'.format(selection, accum)

Use itertools.compress to filter weights by selection.

>>> from itertools import *
>>> compress([1,2,3,4], [1,0,1,1])
<itertools.compress object at 0x00000000027A07F0>
>>> list(compress([1,2,3,4], [1,0,1,1]))
[1, 3, 4]

Answer 2

Manually, you could do it like (I would recommend itertools though):

t = [1,0]
max = 4
ans = [[i,j,k,l] for i in t for j in t for k in t for l in t if i*1+j*2+k*3+l*4 <= max]
#[[1, 1, 0, 0],
# [1, 0, 1, 0],
# [1, 0, 0, 0],
# [0, 1, 0, 0],
# [0, 0, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 0]]