Reducing permutations of many nested loops

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

00000000

02000000

this will be equivalent to:

00001111

00000000

00000020

and

00000020

00000000

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).

Thanks for the reply. I've done some tests:576 iterations from 1,680 iterations (34% original size)31,104 iterations from 90,720 iterations (34% original size)For varying numbers of squares/canvas sizes, so it's a sucessfull optisation reducing permutations to 34% original each time which is super!Is there anyway to make further 'mirror' optimisations with multiple squares? With 2 squares you reduce the loops of the first square, then loop all positions with 2nd square, if you had 3 squares, any way to optimise that?

Tom Gullen 2010-06-17 11:01:32

see my edit above. my previous comment was crude so i deleted it, but basically, do the above (1st quarter x 1st half, 2nd quarter x first half), but for each step, loop also with each permutation of the 3rd square.

maranas 2010-06-17 11:37:35

ansaurus

tags:

views:

answers:

Reducing permutations of many nested loops

related questions