Re: Re: Coding an inverse permutation
- To: mathgroup at smc.vnet.net
- Subject: [mg79170] Re: [mg79113] Re: [mg79078] Coding an inverse permutation
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Fri, 20 Jul 2007 03:25:15 -0400 (EDT)
- References: <200707180652.CAA04270@smc.vnet.net> <469E1148.1040707@wolfram.com> <a851af150707180710m37b35d15r63afae932f6a0920@mail.gmail.com> <12441807.1184858684870.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
Not sure if this would be useful to the OP, but the following augments the
original to a full permutation, then does the same as Carl's code:
unsortedUnion[x_]:=Module[{f},f[y_]:=(f[y]=Sequence[];y);f/@x]
invertPerm[p_] :=
Module[{t = unsortedUnion@Join[p, Range@Max[p]]},
t[[t]] = Range@Length@t; t]
Like Carl's code, the timing should be linear in the maximum element of p.
Bobby
On Thu, 19 Jul 2007 02:24:48 -0500, Carl K. Woll <carlw at wolfram.com> wrote:
> Diana Mecum wrote:
>> Thank you Carl. Would the algorithm give the same results as
>> Ordering[aa]? Diana
>
> Yes, but invperm is faster. For example, here is a large permutation:
>
> perm = Ordering[RandomReal[1,10^6]];
>
> Here I compare invperm and Ordering timings:
>
> In[100]:= r1 = invperm[perm]; // Timing
> r2 = Ordering[perm]; // Timing
> r1 === r2
>
> Out[100]= {0.109,Null}
>
> Out[101]= {0.875,Null}
>
> Out[102]= True
>
> So, invperm is about 8 times faster. This is because Ordering needs to
> sort, while invperm does no sorting. Hence, invperm uses an O(n)
> algorthm, while Ordering uses an O(n log n) algorithm.
>
> Carl Woll
> Wolfram Research
>
>>
>> On 7/18/07, *Carl K. Woll* <carlw at wolfram.com
>> <mailto:carlw at wolfram.com>> wrote:
>>
>> Diana wrote:
>> > Folks,
>> >
>> > I have the following list:
>> >
>> > aa={1, 2, 5, 3, 4, 8, 9, 7, 11, 6, 13, 17, 10, 16, 19, 15, 14,
>> 20, 21,
>> > 23, 25, 12, 29, 31, 18, 22,
>> > 37, 27, 26, 28, 33, 35, 32, 24, 41, 43, 30, 34, 47, 39, 38, 40,
>> 45,
>> > 49, 44, 36, 53, 55, 46, 52,
>> > 59, 51, 50, 56, 57, 61, 62, 42, 67, 71, 48, 58, 65, 63, 64, 68,
>> 69,
>> > 73, 74, 54, 77, 79, 60, 76,
>> > 83, 75, 80, 70, 81, 89, 85, 66, 95, 97, 72, 82, 91, 87}
>> >
>> > I want to figure out a clean way to code its inverse permutation.
>> >
>> > The inverse permutation list would start as follows:
>> >
>> > bb={1,2,4,5,3,10,8,6, ...}
>> >
>> > Since "3" is in position 4 of aa, position 3 of bb will be "4" .
>> > Since "5" is in position 3 of aa, position 5 of bb will be "3" .
>> >
>> > Can someone give me a suggestion as to how to code this?
>> >
>> > Thanks, Diana
>> >
>>
>> I don't think aa qualifies as a permutation, so finding the inverse
>> permutation will be difficult. This is because the list aa only has
>> 88
>> elements, but it contains elements greater than 88. For example, aa
>> contains 91 in position 87, so presumably 87->91. However, as there
>> are
>> only 88 elements in aa, we don't know where 91 goes to.
>>
>> I think a permutation list of length n should contain the numbers 1
>> to n
>> in some permuted order.
>>
>> At any rate, if your list is a permutation list as I defined above,
>> then
>> the following is one way to find the inverse permutation:
>>
>> invperm[p_] := Module[{t=p}, t[[p]]=Range[Length[p]]; t]
>>
>> Carl Woll
>> Wolfram Research
>>
>>
>>
>>
>> --
>> "God made the integers, all else is the work of man."
>> L. Kronecker, Jahresber. DMV 2, S. 19.
>
>
>
--
DrMajorBob at bigfoot.com
- References:
- Coding an inverse permutation
- From: Diana <diana.mecum@gmail.com>
- Coding an inverse permutation