Generating permutation in Python with specific rule
- by twfx
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
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, stop, 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
[1,0,1,0] is the best combination which does not exceeded max_weight 4
My questions are
What's the algorithm which generate the required permutation? Or any suggestion I could generate the permutation?
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?
