Re: Re: Coding an inverse permutation
- To: mathgroup at smc.vnet.net
- Subject: [mg79181] Re: [mg79113] Re: [mg79078] Coding an inverse permutation
- From: DrMajorBob <drmajorbob at bigfoot.com>
- Date: Fri, 20 Jul 2007 03:30:58 -0400 (EDT)
- Organization: Deep Space Corps of Engineers
- 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> <13245146.1184890514811.JavaMail.root@m35>
- Reply-to: drmajorbob at bigfoot.com
Archaeology can be fun, but fast is good too.
Thanks!
Bobby
On Thu, 19 Jul 2007 15:45:40 -0500, Carl Woll <carlw at wolfram.com> wrote:=
> DrMajorBob wrote:
>
>> Not sure if this would be useful to the OP, but the following augment=
s =
>> the original to a full permutation, then does the same as Carl's cod=
e:
>>
>> 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 n=
ew =
> 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 n=
ow =
> 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 numbe=
rs =
>>>> 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