4
$\begingroup$

I have a complicated recursive module which I have memoized. I realised that certain isomorphs of inputs to this function will give the same output. Therefore I decided to memoize all such input-output pairs, each time the function is called with a representative of a new such equivalence class. Here is a much simpler, analogous module:

First without sneakiness:

determinant[m_] := determinant[m] = Module[{localvars},
    If[Length[m] == 1, Return[m[[1, 1]]]];
    Sum[Power[-1, j + 1] m[[1, j]] determinant[
       m[[Complement[Range[Length[m]], {1}], 
         Complement[Range[Length[m]], {j}]]]], {j, 1, Length[m]}]
    ];

And now with sneakiness:

sneakydeterminant[m_] := sneakydeterminant[m] = Module[{answer},
    If[Length[m] == 1, Return[m[[1, 1]]]];
    answer = 
     Sum[Power[-1, j + 1] m[[1, j]] sneakydeterminant[
        m[[Complement[Range[Length[m]], {1}], 
          Complement[Range[Length[m]], {j}]]]], {j, 1, Length[m]}];
    sneakydeterminant[Transpose[m]] = answer;
    answer
    ];

Inspecting the DownValues for each function after calling them seems to indicate that I have succeeded in assigning input-output pairs to the sneakydeterminant function, even while inside its own code.

My question is, whether this is allowed and safe, or have I got away with it just by luck ?

The reason I ask is that this doesn't seem to work in my real example (which I refrained from posting because it is many lines of code long).

Thank you !

$\endgroup$
  • 1
    $\begingroup$ I don't see any problems with it, but I find sneakydeterminant[m_] := sneakydeterminant[m] = sneakydeterminant[Transpose[m]] = .... more clear $\endgroup$ – Dr. belisarius Nov 4 '15 at 14:21
  • $\begingroup$ Aha ! Very nice ! $\endgroup$ – Simon Nov 4 '15 at 17:56
2
$\begingroup$

This is how I would write it:

sneakydeterminant[m_] := sneakydeterminant[m] = 
  sneakydeterminant[Transpose[m]] = 
    If[Length[m] == 1,
      m[[1, 1]]],
      Sum[Power[-1, j + 1] m[[1, j]] sneakydeterminant[
        m[[Complement[Range[Length[m]], {1}], 
          Complement[Range[Length[m]], {j}]]]], {j, 1, Length[m]}]

The only difference is the time at which the new DownValue is added, but it should be equally safe.

$\endgroup$
  • 1
    $\begingroup$ You don't need Module[{answer}, ...] $\endgroup$ – Dr. belisarius Nov 4 '15 at 14:26
  • 1
    $\begingroup$ @belisariusisforth, thanks, missed it, fixed now $\endgroup$ – Marius Ladegård Meyer Nov 4 '15 at 15:18
  • $\begingroup$ Thank you both very much, belisarius and Marius ! I like how you put the other values in the declaration of the function, and how you used the structure of the If statement. I see you also avoided using Module. Is there a similar way to memoize an arbitrary number of equal values of the function ? For instance, suppose that all matrices obtained by permuting the rows and columns like this: m[[permutation, permutation]] were supposed to give the same output ? $\endgroup$ – Simon Nov 4 '15 at 18:03
  • 1
    $\begingroup$ @Simon The question about permutations is an interesting one. Perhaps you may post it as a separate one (once you have checked if it wasn't asked before!) $\endgroup$ – Dr. belisarius Nov 4 '15 at 18:07
  • $\begingroup$ Thank you belisarius is forth. In fact my matrices are really adjacency matrices of graphs, and I would like to represent unlabelled graphs. Therefore these questions and answers seem as if they might have what I need: mathematica.stackexchange.com/questions/23245/… mathematica.stackexchange.com/questions/17658/… $\endgroup$ – Simon Nov 4 '15 at 18:43
1
$\begingroup$

I like this (equivalent) one better:

ClearAll[sd];
t = Transpose;
sd@{} = 1;
sd@m_:= sd@m= sd@t@m= m[[1,1]] /; Length@m == 1
sd@m_:= sd@m= sd@t@m= Sum[m[[1,j]] (-1)^(j + 1) sd@Drop[m,{1},{j}], {j, Length@m}]
$\endgroup$
  • $\begingroup$ Thank you ! I must admit that I find the more verbose version much easier to understand ! $\endgroup$ – Simon Nov 4 '15 at 18:04
  • 1
    $\begingroup$ @Simon, note that using Drop will scale much better than Complement for lagre matrices, so +1 $\endgroup$ – Marius Ladegård Meyer Nov 4 '15 at 21:50
  • $\begingroup$ Thank you Marius ! What do you mean by +1- ? $\endgroup$ – Simon Nov 5 '15 at 8:30
  • $\begingroup$ @Simon He means he upvoted my answer because he has found something of worth in it. I recommend you to the same (meaning: upvotng answers you consider good ones, not necessarily this one :) ). It is just good for future users to know that previous ones considered the content "good" $\endgroup$ – Dr. belisarius Nov 5 '15 at 13:38
  • $\begingroup$ @Simon BTW, it doesn't work as a "one time only" prize. You can upvote all the answers you consider good ones. $\endgroup$ – Dr. belisarius Nov 5 '15 at 13:40

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.