Combinatorial design for minimization problem over binary strings 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?
 A: It seems that the worst case cost over all k-bit binary strings cannot be bounded by a constant. Let us try to argue that the worst case cost is lower bounded by $k/4$.
To keep the ceil and floor issues away, let us assume that $k$ is a multiple of $4$. Let $\pi_1, \ldots, \pi_k$ be the set of permutations that are chosen beforehand. Consider a $k$-bit binary string $B$ picked at random - by choosing each of the $k$ bits to be $0$ or $1$ independently and with equal probability. Consider the event $E$ that in at least one of the $k$ permutations of $B$, the final $k/4$ positions have no zeros. We can find an upper bound on the probability of $E$ as follows. The probability that there are no zeros in the final $k/4$ positions after $B$ is permuted according to $\pi_i$, $i \in [k]$, is $(1/2)^{k/4}$. The probability that there are no zeros in the final $k/4$ positions in at least one of the $k$ permutations of $B$ (which is the probability of $E$) is at most $k (1/2)^{k/4}$ (by union bound).  
With probability $1/2$ the random string $B$ has at least $k/2$ ones. If $B$ has $k/2$ ones, then in any permutation the first $3k/4$ positions will contain at least $k/4$ ones. 
The probability that either $B$ has less than $k/2$ ones or that event $E$ happens is at most $1/2 + k (1/2)^{k/4}$. For sufficiently large $k$, this will go below $1$. Which means, for such $k$, there is a non-zero probability that $B$ has more than $k/2$ ones (hence at least $k/4$ ones in the first $3k/4$ positions in every permutation) and that all the $k$ selected permutations of $B$ have a $0$ in at least one of the final $k/4$ positions. Which means with non-zero probability the cost of $B$ is at least $k/4$. Which then means that there exists some string $B$ with this property.
A: 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.
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}$.
