Re: Swiftest code to turn list of ordered pairs into Markov matrix

*To*: mathgroup at smc.vnet.net*Subject*: [mg29718] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: BobHanlon at aol.com*Date*: Wed, 4 Jul 2001 03:08:47 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

In a message dated 2001/7/3 5:11:42 AM, SChandler at Central.UH.Edu writes: >Suppose one has a list of ordered pairs oplist such as >{{1,5},{1,6},{2,3},{2,3} ... }. All the values in the list are positive >integers. The highest value in oplist is known to be some value z. > >Now one wishes to form a matrix such that the value at element i,j is equal >to >Count[oplist,{i,j}]. One terribly slow way to do this is > >Table[Count[oplist,{i,j}],{i,1,z},{j,1,z}] > >A faster way to do this is as follows: >Fold[ReplacePart[#,Extract[#,#2]+1,{#2}]&,Table[0,{z},{z}],oplist] > >Does anyone have a considerably faster way? A speed up of 100% or more >would >be very helpful. > >For what it's worth Count[oplist,{something_,_}] is the same for all values >of something. > >P.S. The problem arises in converting a representation of a directed graph >into a Markov transition matrix. > Your second method should read: Fold[ReplacePart[#,Extract[#,#2]+1,#2]&,Table[0,{z},{z}],oplist] A faster approach is Fold[ReplacePart[#, #2[[2]], #2[[1]]]&, Table[0, {z}, {z}], {First[#], Length[#]}& /@ Split[Sort[oplist]]] Bob Hanlon Chantilly, VA USA