Bill Dolinar
1/26/2006 5:48:00 PM
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