Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ string permutations (static, chosen beforehand) and then, the cost of an input string $B$ is the minimum cost of the $k$ permutations of $B$.
Given $k$, we want to choose $k$ string permutations in order to minimize the worst case over any input string of length $k$. I have been working on this problem for a couple of weeks and I have found that (almost symmetric) latin squares work quite well. For example, for $k$ = 8, the following set of permutations:
0 1 2 3 4 5 6 7
1 4 5 6 0 2 7 3
2 5 6 1 3 7 0 4
3 6 1 4 7 0 2 5
4 0 3 7 5 6 1 2
5 2 7 0 1 3 4 6
6 7 0 5 2 4 3 1
7 3 4 2 6 1 5 0
has a worst case of 2 over every input (in my program, the permutations indicate the destination of the current symbol rather than the symbol that moves to the current destination). However, it already takes several minutes to compute and I will need to generalize this up to $k$ = 128.
I have been reading a bit about combinatorial designs but I am not mathematician, so I'm not sure what could work well. Any ideas?