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$
2
  • 1
    $\begingroup$ I don't see any problems with it, but I find sneakydeterminant[m_] := sneakydeterminant[m] = sneakydeterminant[Transpose[m]] = .... more clear $\endgroup$ Nov 4, 2015 at 14:21
  • $\begingroup$ Aha ! Very nice ! $\endgroup$
    – Simon
    Nov 4, 2015 at 17:56

2 Answers 2

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$
6
  • 1
    $\begingroup$ You don't need Module[{answer}, ...] $\endgroup$ Nov 4, 2015 at 14:26
  • 1
    $\begingroup$ @belisariusisforth, thanks, missed it, fixed now $\endgroup$ Nov 4, 2015 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, 2015 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$ Nov 4, 2015 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, 2015 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$
5
  • $\begingroup$ Thank you ! I must admit that I find the more verbose version much easier to understand ! $\endgroup$
    – Simon
    Nov 4, 2015 at 18:04
  • 1
    $\begingroup$ @Simon, note that using Drop will scale much better than Complement for lagre matrices, so +1 $\endgroup$ Nov 4, 2015 at 21:50
  • $\begingroup$ Thank you Marius ! What do you mean by +1- ? $\endgroup$
    – Simon
    Nov 5, 2015 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$ Nov 5, 2015 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$ Nov 5, 2015 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.