Function Range Trick

Revision en6, by usernameson, 2017-03-20 07:57:58

Disclaimer

I do not know if this technique has another name. I came up with it to solve specific types of problems but it probably has been done by many others before.

The situation

Assume we are given a sequence of numbers a1, a2, ..., an - 1, an and we have a function f that is well defined for all sequences of numbers with the property f(b1, ..., bm) = f(f(b1, ..., bm - 1), bm) for any sequence b and the range of f has size K, which is relatively small. Our goal is to rearrange the numbers a1, ..., an so that when the sequence is entered into f in this order the value of f is optimised (minimised or maximised).

The solution

If we try to brute force all permutations of the sequence there are n! options which is usually too slow. However what we can do is use dynamic programming and for each sequence ending in aj with m terms store all possible values of f. Since we know the range of f is K at each step we are storing at most K terms.

Cost analysis

To calculate all possible values of f for a sequence ending in aj with m + 1 terms given we have calculated all possible values for f with sequence with m terms we need at most (n - 1)K calculations. Doing this for each term to calculate all possible values for f with a sequence of m + 1 terms gives at most n(n - 1)K calculations. Doing it n times since we need sequences of length n gives at most n2(n - 1)K. Finally to find the optimised value requires at most nK more calculations. So at worst we have n2(n - 1)K + nK calculations.

Noticing the situation

The nature of the function is what determines whether this situation occurs. If the function is based on bitwise operations and the values of the sequence are small there is a good chance that this technique applies. Also if the function is based on arithmetic modulo N where N is small this technique might also apply.

Tags dp, math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English usernameson 2017-03-21 04:21:24 0 Added a worked example (published)
en9 English usernameson 2017-03-21 04:19:46 2 Tiny change: '\n\nCode\n~~~~~\n#' -> '\n\nCode\n\n~~~~~\n#'
en8 English usernameson 2017-03-21 04:18:25 1 Tiny change: 'ode\n~~~~~~\n#in' -> 'ode\n~~~~~\n#in'
en7 English usernameson 2017-03-21 04:17:11 3310 Added a worked example (saved to drafts)
en6 English usernameson 2017-03-20 07:57:58 0 (published)
en5 English usernameson 2017-03-20 07:56:20 14
en4 English usernameson 2017-03-20 07:54:00 1 Tiny change: 'f(f(b_{1},ldots,b_{m' -> 'f(f(b_{1},\ldots,b_{m'
en3 English usernameson 2017-03-20 07:53:32 34
en2 English usernameson 2017-03-20 07:52:22 32
en1 English usernameson 2017-03-20 07:34:54 1919 Initial revision (saved to drafts)