1
$\begingroup$

I would like to find the maximum of some objective function over all possible permutations

(* Memory inefficient solution *)
Max[obj/@Permutations[lst]]

(* Outout: SystemException["MemoryAllocationFailure"] *)

While this computation might be intractably slow $O(n!)$, it should have $O(n)$ space for lst of size $n$.

Is there an efficient way to only cache the max seen so far? Thanks

Here is a standalone trivial example for the purposes of testing

n = 10;
l = Range[n];

Max[l . # & /@ Permutations[l]]
(* 385 *)
``` 
$\endgroup$
3
  • 5
    $\begingroup$ There is the aptly named ResourceFunction["MaximizeOverPermutations"] $\endgroup$ Apr 10 at 3:42
  • $\begingroup$ Related: mathematica.stackexchange.com/questions/201333/… $\endgroup$
    – Adam
    Apr 11 at 23:57
  • $\begingroup$ Is "The number of permutations of n objects scales very quickly with n. The default "Enumerate" method should not be used with n≳12 in order to prevent memory overflow" from the Possible Issues a concern since the OP asks for O(n) in space? I suppose the linked question may answer this since it is ostensibly the source code for the function. $\endgroup$
    – Adam
    Apr 12 at 0:02

0

Your Answer

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

Browse other questions tagged or ask your own question.