#### 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.
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.
