Once you assume that an operation is to be done
in place, swapping items at the front or at
the back are the same. There is free space
at the back and none at the front, but neither
matter if you are just swapping.
As you'd indicated, in general the operation is:
name=: p{name
where p is a permutation and p=&#name . The
challenge then is to do it without using an
excessive amount of temps. The tools already
exist: compute c=: C. p , and for each cycle
just one temp (of item size) is needed.
But wait: you have to compute C.p using only
O(1) space. I guess you can do it by traversing
the cycles without materializing them. e.g.
p=: 10 ?. 10
p
6 9 1 4 0 2 3 8 7 5
record 0, store item 0
0{p is 6, so put item 6 into item 0
6{p is 3, so put item 3 into item 6
3{p is 4, so put item 4 into item 3
4{p is 0, so put item 0 into item 4
This completes the first cycle.
Hmm, doing name=: p{name in O(1) space and O(n)
time looks challenging. At this point I don't see
how. I think I need one bit per item to indicate
that the item has already been processed. I guess
I could do it by cheating, using the space in p and
restoring it afterwards.
----- Original Message -----
From: greg heil <[EMAIL PROTECTED]>
Date: Thursday, July 13, 2006 10:42 am
Subject: Re: [Jprogramming] special coding for stack operations
> On 7/13/06, R&S HUI <[EMAIL PROTECTED]> wrote:
> > For swapping items, x A. y has a high "gee whiz" factor, but
> (<i,j)C. y is more practical. For example, to swap last two
> items, one could say 1&A. or (<_1 _2)&C. . To swap the first
> two items, (<0 1)&C. does it. To do it using A. is less
> straightforward.
> Yes. But assuming in place operations are easier at the distal end...?
> The A. is quite perspicuous - more terse, much like o. For stack
> operations, one end is good enough.
>
> If you could do in place swap operations more generically say those
> which preserved element sizes and array shape ... well the whole world
> of group theory is your oyster. i could use a lot of efficient in
> place operations, eg moving sprites around in a bitmap...
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
