MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: coordinates form 3Dplot/Densitygraphics
  • Next by Date: RE: Derivative of multiargument function
  • Previous by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix
  • Next by thread: Re: Swiftest code to turn list of ordered pairs into Markov matrix