Reducing permutations of many nested loops
I decided to do an image to explain this better, I just want to check my thinking is ok, and that I can reduce total permutations by 75%:
alt text http://www.freeimagehosting.net/uploads/45e5c开发者_如何学C6b05e.gif
you are reducing the number of permutations, but not by 75%, since all possible positions of the small square fill up a 6x6 square, and your "quarter" fills up a 4x4 square.
Since there are "overlaps" to your quarters, you are actually adding a little permutations. Since your quarter is 4x4, you have 4 squares overlapping in the middle column, and another four in your middle row.
Still, this is less than actually computing for each small square.
also, you could further increase performance with 2 squares by doing this:
let's say you have 2 squares, 1 & 2. if your square is:
11110000
11110000
00000000
02000000
this will be equivalent to:
00001111
00001111
00000000
00000020
and
00000020
00000000
00001111
00001111
so, you could loop through all permutations of 1 in the first quarter of the grid, against all permutations of 2 in the FIRST HALF (left) of the grid. do this for quarters 1 and 2 (where quarter 1 is upper-left, and quarter 2 is upper right).
精彩评论