Re: Re: Coding an inverse permutation
- To: mathgroup at smc.vnet.net
- Subject: [mg79177] Re: [mg79113] Re: [mg79078] Coding an inverse permutation
- From: Carl Woll <carlw at wolfram.com>
- Date: Fri, 20 Jul 2007 03:28:53 -0400 (EDT)
- References: <200707180652.CAA04270@smc.vnet.net> <469E1148.1040707@wolfram.com> <a851af150707180710m37b35d15r63afae932f6a0920@mail.gmail.com> <12441807.1184858684870.JavaMail.root@m35> <op.tvp7hye9qu6oor@monster.gateway.2wire.net>
DrMajorBob wrote:
> 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
Note that the fastest way to get an unsorted union now is to use the new
version 6 function Tally:
uu2[x_]:=Tally[x][[All,1]]
Here is a test of the two versions:
In[172]:=
data = RandomInteger[10^7, 10^6];
In[173]:=
r1 = unsortedUnion[data]; // Timing
r2 = uu2[data]; // Timing
r1 === r2
Out[173]= {11.766,Null}
Out[174]= {1.593,Null}
Out[175]= True
The unsortedUnion function you use is an old idea of mine, but it is now
only interesting from an archeological perspective.
Carl
>
> 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.
>>
>>
>>
>>
>
>
>
- References:
- Coding an inverse permutation
- From: Diana <diana.mecum@gmail.com>
- Coding an inverse permutation