4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ciao Jun 3 '14 at 5:47
  • $\begingroup$ Apologies - updated. $\endgroup$ – martin Jun 3 '14 at 6:09
  • 2
    $\begingroup$ 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. $\endgroup$ – ciao Jun 3 '14 at 6:20
9
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ Much more efficient - thank you :) $\endgroup$ – martin Jun 3 '14 at 6:13
  • $\begingroup$ @martin: My pleasure. On a quick y = 500; m = 250; test, it was over 1500X faster, and of course much more frugal on memory... $\endgroup$ – ciao Jun 3 '14 at 6:19
  • $\begingroup$ My one shut down the kernel at y=1000; m=500 !! :( - Much better! many thanks!! $\endgroup$ – martin Jun 3 '14 at 6:21
  • $\begingroup$ @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! $\endgroup$ – ciao Jun 3 '14 at 6:23
  • $\begingroup$ Thanks for your help - it has made things much easier!! :) $\endgroup$ – martin Jun 3 '14 at 6:25
9
$\begingroup$

Different approach:

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

Not so fast but short.

MatrixForm @ %

enter image description here

$\endgroup$
  • $\begingroup$ Very concise - doesn't seem to work for me though ... $\endgroup$ – martin Jun 3 '14 at 6:28
  • $\begingroup$ @martin what do you mean? :) $\endgroup$ – Kuba Jun 3 '14 at 6:29
  • $\begingroup$ Ah ... whoops !! :) $\endgroup$ – martin Jun 3 '14 at 6:30
  • $\begingroup$ FYI: you don't need Normal before applying MatrixForm. $\endgroup$ – Mr.Wizard Jun 3 '14 at 12:10
  • $\begingroup$ @Mr.Wizard I must admit I was to lazy to correct this :p $\endgroup$ – Kuba Jun 3 '14 at 12:12
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.