How to handle a sparse array of lists

Question

I have data in the form of a sparse array of lists. For example:

{{76, 17} -> {17803}, {24, 14} -> {18625, 311571, 440371, 818848, 
   2010244, 2317818}, {64, 99} -> {19421, 269349, 397997, 440343, 
   503977, 511172, 1600938, 1656131, 1849185, 1849187, 1974513, 
   2045184, 2065062, 2319929}}

The indices are pairs of integers in the range {0,...,S}^2.

It seems as it is not possible to store this as a sparse array in Mathematica, as I get the error

SparseArray::valnl: "The value specified by the rule {76,17}->{17803} should not be a List. "

How would I create an object which provides:

• quick access to the list corresponding to an entry - for example something like a[[i,j]] (default is the empty list).
• create a (dense) matrix with the largest list element (default 0)
• create a (dense) matrix with the largest list element not bigger than a given constant

Update: Example regarding the last point. If the constant would be 500000, than the entry for {76,17} should be 17803, for {24,14} 440371, for {64,99} 440343 and for all other it should be 0.

Answer 1

Apologies if I've misunderstood your questions. I've never used Dispatch before, as suggested by Kuba in the comments, but it seems to be the right tool for the problem if speed is your concern.

First off, I hope it's clear that accessing the list corresponding to an index pair is as straightforward is applying the rules list for pattern replacement:

rules = {{76, 17} -> {17803}, {24, 14} -> {18625, 311571, 
     440371, 818848, 2010244, 2317818}, {64, 99} -> {19421, 269349, 
     397997, 440343, 503977, 511172, 1600938, 1656131, 1849185, 
     1849187, 1974513, 2045184, 2065062, 2319929}}
drules = Dispatch[rules~Append~(_ -> {})]
(* Note that I've added an additional rule at the end for the "default case" *)
{64, 99} /. drules

(* returns {19421, 269349, 397997, 440343, 503977, 511172, 1600938, 1656131, \
1849185, 1849187, 1974513, 2045184, 2065062, 2319929} *)
{100, 100} /. drules
(* returns {} *)

You can easily write it as a function.

Regarding creating "a (dense) matrix with the largest list element (default 0)" - if I've understood correctly - you could do:

Normal@SparseArray@MapAt[Max, rules, {All, -1}]

And for the "create a (dense) matrix with the largest list element not bigger than a given constant" bit:

With[{c = 500000}, 
  SparseArray@
   MapAt[Max@Select[#, Function[x, x <= c]] &, 
    rules, {All, -1}]];

% // ArrayRules 
(* gives {{24, 14} -> 440371, {64, 99} -> 440343, {76, 17} -> 17803, {_, _} -> 
  0} *)

If your lists are in ascending order (as they are in your example), then you could replace the Select with TakeWhile and the Max with Last. I imagine that might be faster.

Answer 2

You could define a function f that does the lookup for you:

rules = {{76, 17} -> {17803},
         {24, 14} -> {18625, 311571, 440371, 818848, 2010244, 2317818},
         {64, 99} -> {19421, 269349, 397997, 440343, 503977, 511172, 1600938, 1656131, 1849185, 1849187, 1974513, 2045184, 2065062, 2319929}};

Clear[f];
rules /. (a_ -> b_) :> (f[Sequence @@ a] = b);
f[_, _] = {};

Try it out:

f[76, 17]
(*    {17803}    *)

f[1, 2]
(*    {}    *)

Generate a matrix with largest elements not larger than m (set m=∞ for using largest elements):

With[{m = 500000},
  rules /. (a_ -> b_) :> (a -> Max[Select[b, # <= m &]])] /. -∞ -> 0
(*    {{76, 17} -> 17803,
       {24, 14} -> 440371,
       {64, 99} -> 440343}    *)

% // SparseArray
(*    sparse array with dimensions 76x99    *)