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: Use
[itertools.product](http://docs.python.org/2/library/itertools.html#itertools.compress)
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](http://docs.python.org/2/library/itertools.html#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]
    

