Re: Coding an inverse permutation
- To: mathgroup at smc.vnet.net
- Subject: [mg79113] Re: [mg79078] Coding an inverse permutation
- From: "Carl K. Woll" <carlw at wolfram.com>
- Date: Thu, 19 Jul 2007 03:24:48 -0400 (EDT)
- References: <200707180652.CAA04270@smc.vnet.net> <469E1148.1040707@wolfram.com> <a851af150707180710m37b35d15r63afae932f6a0920@mail.gmail.com>
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.
- References:
- Coding an inverse permutation
- From: Diana <diana.mecum@gmail.com>
- Coding an inverse permutation