# Efficient matrix / array generation

What is the most efficient way of generating the following matrix?

$\left( \begin{array}{ccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & \dots\\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & \dots\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 & \frac{1}{3} & \dots\\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & 0 & 0 & \dots\\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & 0 & \dots\\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0 & \dots\\ \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \dots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array} \right)$

where the first line begins $\{1,0,1,0,1,0,1,0,1,0,1,0\dots\}$

The second: $\{\frac{1}{2},\frac{1}{2},0,0,\frac{1}{2},\frac{1}{2},0,0,\frac{1}{2},\frac{1}{2},0,0\dots\}$

The third: $\{\frac{1}{3},\frac{1}{3},\frac{1}{3},0,0,0,\frac{1}{3},\frac{1}{3},\frac{1}{3},0,0,0\dots\}$

and so on.

My effort is

y = 14; m = 7;
Table[Take[Drop[Take[Flatten[ConstantArray[Flatten[Riffle[Array[0 &, {n, n}],
Array[1 &, {n, n}]]], y - n]], y], n], y - m]/n, {n, 1, m}] // MatrixForm


but calculates too many unnecessary terms.

-
Adding at least some minimal description of what it is you're trying to do (e.g. the "rules" for elements), instead of having readers decode it, might elicit more response. –  rasher Jun 3 '14 at 5:47
Apologies - updated. –  martin Jun 3 '14 at 6:09
No worries, it just helps the reader to be clear on intent (like: "Is that pattern really the pattern...") without having to figure out the code. –  rasher Jun 3 '14 at 6:20

This should be pretty efficient (still generates a few extra elements, but I'd venture the overhead of short-circuiting that would exceed the overhead of the trimming):

y = 14; m = 7;

array=Take[Flatten[ConstantArray[#, Ceiling[(y - m)/Length@#]]], y - m] & /@
Table[Join[ConstantArray[1/row, row], ConstantArray[0, row]], {row, 1, m}];

array//MatrixForm


-
Much more efficient - thank you :) –  martin Jun 3 '14 at 6:13
@martin: My pleasure. On a quick y = 500; m = 250; test, it was over 1500X faster, and of course much more frugal on memory... –  rasher Jun 3 '14 at 6:19
My one shut down the kernel at y=1000; m=500 !! :( - Much better! many thanks!! –  martin Jun 3 '14 at 6:21
@martin: Yep, that would eat memory pretty quickly using the method you posted. I just did a 5000 x 2500 on a netbook so little RAM, and no issues, took about a second (so ~0.1 sec on a "real" machine). Thanks for the accept! –  rasher Jun 3 '14 at 6:23
Thanks for your help - it has made things much easier!! :) –  martin Jun 3 '14 at 6:25

Different approach:

SparseArray[{i_, j_} :> 1/i /; Mod[j, 2 i, 1] <= i, {7, 7}];


Not so fast but short.

MatrixForm @ %


-
Very concise - doesn't seem to work for me though ... –  martin Jun 3 '14 at 6:28
@martin what do you mean? :) –  Kuba Jun 3 '14 at 6:29
Ah ... whoops !! :) –  martin Jun 3 '14 at 6:30
+1, that's pretty! –  rasher Jun 3 '14 at 6:41
FYI: you don't need Normal before applying MatrixForm. –  Mr.Wizard Jun 3 '14 at 12:10

On my machine this is about twice as fast as rasher's present code:

f[n_Integer] :=
With[{split = Quotient[n, 2]},
Join[
Array[PadRight[#, n, #] &[Join @@ (ConstantArray[{1/#, 0}, #]\[Transpose])] &, split],
LowerTriangularize[ConstantArray[1/Range[split + 1, n], n]\[Transpose], split]
]
]

f[9] // MatrixForm


$\left( \begin{array}{ccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{1}{4} \\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & 0 & 0 & 0 \\ \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0 & 0 & 0 \\ \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & \frac{1}{7} & 0 & 0 \\ \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & \frac{1}{8} & 0 \\ \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} & \frac{1}{9} \end{array} \right)$

The optimization is to recognize that everything in the bottom half of the array is equivalent to a simpler form easily produced with LowerTriangularize, and only the top half is generated by a slower cyclic method.

This simpler form is approximately equivalent to rasher code in performance, and a bit more terse:

f2[n_Integer] :=
Array[PadRight[#, n, #] &[Join @@ (ConstantArray[{1/#, 0}, #]\[Transpose])] &, n]


The simpler function updated to allow generation of different shapes of arrays:

f2[n_, m_] :=
Array[PadRight[#, n, #] &[Join @@ (ConstantArray[{1/#, 0}, #]\[Transpose])] &, m]


I'm too tired to extend f likewise at the moment.

-
Wow - super-fast!! :) –  martin Jun 3 '14 at 7:55
Great code - thank you :) –  martin Jun 3 '14 at 8:02
@martin You're welcome. Let me know if you discover anything wrong with it. –  Mr.Wizard Jun 3 '14 at 8:03
@ Mr.Wizard, Will do :) –  martin Jun 3 '14 at 8:03
Interesting: only slightly faster when generating a square matrix, considerably slower to get to row-subsets (as OP example). +1 in any case! –  rasher Jun 3 '14 at 8:09