Function Range Trick
Difference between en5 and en6, changed 0 character(s)
#### 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 $a_{1},a_{2},\ldots,a_{n-1},a_{n}$ and we have a function $f$ that is well defined for all sequences of numbers with the property $f(b_{1},\ldots,b_{m}) = f(f(b_{1},\ldots,b_{m-1}),b_{m})$ for any sequence b and the range of $f$ has size $K$, which is relatively small. Our goal is to rearrange the numbers $a_{1},\ldots,a_{n}$ 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 $a_{j}$ 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 $a_{j}$ 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 $n^2(n-1)K$. Finally to find the optimised value requires at most $nK$ more calculations. So at worst we have $n^2(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.

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)