From: Bill Dolinar Date: 2006-01-27T02:48:09+09:00 Subject: Re: [QUIZ.SUMMARY] Grid Folding (#63) On Jan 26, 2006, at 8:35 AM, Andrew Dudzik wrote: >> >> I think there is still some interesting math to pull out of this >> problem. For example, Andrew Dudzik ponders: "There are never two >> sequences that give the same perm. Does anybody know why this is? >> Seems like an interesting math problem." Myself, I wonder if he's >> right. >> > > I think that this is true, and that it follows from Bill Dolinar's > solution > for check_fold--the last fold is always uniquely determined by > picking some > x and y coordinates and looking at the numbers on the top and > bottom of the > stack--if, say, 4 and 7 are on opposite sides of the folded paper, > they must > have been in the same sheet one fold ago--the direction of this > fold is > determined by the relative orientation of 4 and 7 in the original, > unfolded > paper. > > Since there is only ever one possible direction to unfold, there > can only be > at most one sequence of unfolds that gives the desired 1--n^2 pattern. > Hence there is at most one sequence of folds that produces a given > permutation. When I was testing my solution for check_fold I found that it was very fast at going through the unfolding. I ran a test on the unfolding the 2048x2048 data and found that I could run unfold a thousand times in about 2.5 seconds. Quite the difference compared to fold running once in about 160 seconds. With the unfold being so fast, one would think there must be some way to speed up folding considerably. I spent some time trying to find a pattern and came up with formulas for the first fold where given the array index it gave the new index, but when considering layers as well on the second fold it made my head spin. Thinking about it though, in the algorithm to unfold you only have to consider two elements of the array each time you unfold. For folding you have to consider every element of the array for each fold. Bill