Merging SparseArrays (or normal arrays)

Question

I have a list of SparseArrays, and I want to combine them into one array that concatenates their rules. I don't want to connect them together like ArrayFlatten does, but rather to combine the defined values.

I'm working to look at a function that maps $\mathbb{N}$ to a list of points in $\mathbb{N^2}$, and I want to look at plots of the function's outputs ensure that all values in a relevant region of $\mathbb{N^2}$ are present in the image of at least one application. (There's other stuff going on in the SparseArray values too.) So I'm taking the outputs of the function as SparseArrays, and combining them.

This is the best solution I've got so far. It pretty much takes the rules from each input array and flattens them, with a substitution rule to get rid of defaults. But it seems that this should be a 1-liner; am I missing something obvious?

combineSparseArrays[arrays_, default_] :=
  SparseArray[
    Flatten[
      (ArrayRules/@arrays) /. ({_Blank,_Blank}->_) -> Nothing,
      1],
    Automatic,
    default]

As a note, my first version used normal arrays [as lists of lists] and combined them using a Do loop that set elements in the output array individually. The SparseArray version is, unsurprisingly, rather faster.

Edit to add example:

Here's an example input and expected output.

The easy-to-read version: as a list of lists of rules in grid form, where each row represents one input SparseArray:

{1,3}->28   {2,3}->35   {3,3}->54   {_,_}->0
​{1,4}->65   {2,4}->72   {3,4}->91   {_,_}->0
​{1,5}->126  {2,5}->133  {3,5}->152  {4,5}->189  {_,_}->0
​{1,6}->217  {2,6}->224  {3,6}->243  {4,6}->280  {5,6}->341  {_,_}->0

Same ruleset, in InputForm for easy copy/paste:

{SparseArray[Automatic, {3, 3}, 0, {1, {{0, 1, 2, 3}, {{3}, {3}, {3}}}, {28, 35, 54}}],
 SparseArray[Automatic, {3, 4}, 0, {1, {{0, 1, 2, 3}, {{4}, {4}, {4}}}, {65, 72, 91}}],
 SparseArray[Automatic, {4, 5}, 0, {1, {{0, 1, 2, 3, 4}, {{5}, {5}, {5}, {5}}}, {126, 133, 152, 189}}],
 SparseArray[Automatic, {5, 6}, 0, {1, {{0, 1, 2, 3, 4, 5}, {{6}, {6}, {6}, {6}, {6}}}, {217, 224, 243, 280, 341}}]}

The expected output should be equal to the following (which I reformatted for ease of reading):

SparseArray[{{1,3}->28, {1,4}->65, {1,5}->126,
             {1,6}->217, {2,3}->35, {2,4}->72,
             {2,5}->133, {2,6}->224, {3,3}->54,
             {3,4}->91, {3,5}->152, {3,6}->243,
             {4,5}->189, {4,6}->280, {5,6}->341,
             {_,_}->0}]

In answer to klgr's question: Yes, it is possible for there to be duplicates, although there aren't in that example. These may be resolved by using either input array or something, but not by summation (although that's a clever idea!).

That did give me the idea of combining them into a 3d SparseArray using Transpose, like this:

Transpose[SparseArray[SparseArray[#, Max /@ Transpose[Dimensions /@ arrays]] & /@ arrays], {3,1,2}]

My plan had been to treat this as a 2d array of lists, and use SelectFirst to get the first non-default element, but so far my attempts to do that have crashed the kernel.

Answer 1

Update: In version 10 an later versions you can use Association and Merge to get something similar to combineF1:

MatrixForm @ Map[ToExpression, 
  SparseArray[Normal @ Merge[ToString][Association[Most @ ArrayRules @ #]&/@ arrays]], -1] 

or, an alternative form for combineF2

MatrixForm @ 
  SparseArray[Normal @ Merge[First][Association[Most @ ArrayRules @ #]&/@ arrays]]

Original post:

For the general case where the arrays to be combined may have different dimensions and their non-zero positions may intersect, if you need to collect repeated entries in a list, you need more than a 1-liner.

ClearAll[combineF1]
combineF1 = Module[{out}, System`SetSystemOptions["SparseArrayOptions" ->
     {"TreatRepeatedEntries" -> (ToString[{##}] &)}];
    out = Map[ToExpression, SparseArray[Join @@ (Most /@ ArrayRules /@ #)], -1] ;
    System`SetSystemOptions["SparseArrayOptions" -> {"TreatRepeatedEntries" -> First}]; 
    out] &;

Example:

arrays = {SparseArray[{{1, 3} -> 28, {2, 3} -> 35, {3, 3} -> 54}], 
   SparseArray[{{1, 4} -> 65, {2, 4} -> 72, {3, 4} -> 91}], 
   SparseArray[{{1, 5} -> 126, {2, 5} -> 133, {3, 5} -> 152, {4, 5} -> 189}], 
   SparseArray[{{1, 6}-> 217, {2, 6}-> 224, {3, 6}-> 243, {4, 6}-> 280, {5, 6}-> 341}],
   SparseArray@UpperTriangularize[Partition[Range[16], 4]]};

where I added an array to OP's list of arrays to get an example where non-zero positions are not disjoint.

combineF1@arrays // MatrixForm

Note 1: In the special case where the non-zero positions of the input arrays do not intersect, you can simply use a combination of Plus@@#& and PadRight:

arrays2 = Most[arrays];
Plus@@PadRight[arrays2]

which is the same as what we get using `combineF1:

combineF1@arrays2 // MatrixForm

Note 2: For one reading of your requirement

I want to look at plots of the function's outputs ensure that all values in a relevant region of N^2 are present in the image of at least one application.

perhaps you can use much simpler

Unitize[Plus @@ PadRight[arrays] ] // MatrixForm

where 1s indicate positions covered by at least one application.

Note 3: With the default setting ("SparseArrayOptions" -> {"TreatRepeatedEntries" -> First}), only the first of repeated entries is used by 'SparseArray', the rest are ignored. If this is ok for your use cases, then you can use

ClearAll[combineF2]
combineF2 = SparseArray[Join @@ (Most /@ ArrayRules /@ #)] &;

combineF2 @ arrays // MatrixForm

Answer 2

SparseArray[Union @@ ArrayRules /@ arrayList] might be convenient in this case, because Union only returns distinct elements, so one of the default patterns will automatically be dropped.

(s1 = SparseArray[{{i_, i_} -> 1}, {5, 5}]) // Normal
(s2 = SparseArray[{{i_, j_} /; j == i - 1 -> 2}, {5, 5}]) // Normal
(union = SparseArray[Union @@ ArrayRules /@ {s1, s2}]) // Normal

(* Out:
{{1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}}
{{0, 0, 0, 0, 0}, {2, 0, 0, 0, 0}, {0, 2, 0, 0, 0}, {0, 0, 2, 0, 0}, {0, 0, 0, 2, 0}}
{{1, 0, 0, 0, 0}, {2, 1, 0, 0, 0}, {0, 2, 1, 0, 0}, {0, 0, 2, 1, 0}, {0, 0, 0, 2, 1}}
*)

I haven't tested it extensively though.

You might also be interested in the fact that the default value pattern is always returned last by ArrayRules, so ArrayRules[#][[;;-2]]& would return only the rules for explicitly defined elements.