Services & ResourcesWolfram ForumsMathGroup Archive

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

Swiftest code to turn list of ordered pairs into Markov matrix

• To: mathgroup at smc.vnet.net
• Subject: [mg29683] Swiftest code to turn list of ordered pairs into Markov matrix
• From: "Seth Chandler" <SChandler at Central.UH.Edu>
• Date: Tue, 3 Jul 2001 04:40:37 -0400 (EDT)
• Organization: University of Houston
• Sender: owner-wri-mathgroup at wolfram.com

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

• Follow-Ups:
  • Re: Swiftest code to turn list of ordered pairs into Markov matrix
    • From: "Fred Simons" <f.h.simons@tue.nl>
  • Re: Swiftest code to turn list of ordered pairs into Markov matrix
    • From: Daniel Lichtblau <danl@wolfram.com>