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

*To*: mathgroup at smc.vnet.net*Subject*: [mg29701] Re: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix*From*: Rob Pratt <rpratt at email.unc.edu>*Date*: Wed, 4 Jul 2001 03:08:26 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Perhaps you can modify the FromOrderedPairs command in the DiscreteMath`Combinatorica` package. FromOrderedPairs creates a graph, but you can do Edges[FromOrderedPairs[oplist]] to get the adjacency matrix. The Edges[] matrix has entries in {0, 1}, so some modification is needed if you want to count duplicate edges. Rob Pratt Department of Operations Research The University of North Carolina at Chapel Hill rpratt at email.unc.edu http://www.unc.edu/~rpratt/ On Tue, 3 Jul 2001, Seth Chandler wrote: > 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. > > Thanks, > > Seth J. Chandler > Associate Professor of Law > University of Houston Law Center