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?



Combinatorial design for minimization problem over binary strings
In fact, you cannot do better than $k-2\sqrt{k\log k}$, i.e., for any $k$ permutations, there is a 0-1 sequence on which the cost of any permutation is at least this much. The prove is a simple application of known results about the [Set Cover problem](http://en.wikipedia.org/wiki/Set_cover_problem).


Consider the last $t=\sqrt{k\log k}$ positions in each permutation, these give $k$ sets of size $t$. We want to hit each of them with an element from our base set, this is called the Hitting Set problem and its dual is the Set Cover problem. You can read more details about them on Wikipedia, the important thing is that there is a fractional hitting set of size $k/t$ and since the integrality gap of the problem is at most $\log k$, there is a hitting set of size $(k\log k)/t$.


This means that we can select $(k\log k)/t$ positions such that any permutation contains at least one of them. If we set these positions to be 0's and the others to be 1's, then in any permutation there is a 0 somewhere towards the back and there are many 1's everywhere, a simple calculation gives a cost of at least $k-t-(k\log k)/t=k-2\sqrt{k\log k}$.


