| Re: Most elegant syntax for inverting a permutation? |
|
 |
|
 |
|
 |
|
 |
Group: comp.lang.fortran · Group Profile
Author: Richard HarterRichard Harter Date: Oct 6, 2007 20:44
On Sat, 06 Oct 2007 22:05:19 GMT, Oskar Enoksson
nowhere.org> wrote:
>Richard Maine wrote:
>> Oskar Enoksson nowhere.org> wrote:
>> >>> I was pretty satisfied when realized I could avoid the need for an extra
>>> array using a forall loop as follows:
>>>
>>> FORALL(I=1:N)
>>> P(P(I)) = I
>>> END FORALL
>>
>> Don't be so sure that this aviods the extra array. FORALL is notorious
>> for often involving temporary arrays in its implementation. There may
>> well be an extra array here, even though you don't "see" it in the code.
>
>Yes that I'm aware of. I'm just looking for an clear, compact syntax
>that does the job.
>
>I even guess it's impossible to avoid O(N) extra storage when inverting
>a permutation, except for special classes of permutations.
That depends upon the price you are willing to pay. You can
invert a permutation with no extra storage provided that you are
willing to use an O(n*log(n)) algorithm.
Richard Harter, cri@ tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
But the rhetoric of holistic harmony can generate into a kind of
dotty, Prince Charles-style mysticism. -- Richard Dawkins
| 
