Let $S$ be the set of binary strings of length $n$, i.e. each $x\in S$ is a string whose each entry is a $0$ or a $1$. Let $W(x)$ be the Hamming weight of $x\in S$ i.e. $W(x)$ is the number of ones in $x$. I am looking for a formula for a bijection $f: S\to S$ which shuffles a lot of vertices based on Hamming weight. For example, say $x\in S$ with $W(x)=w$ is mapped to say $y$ with $W(y)=w-2$ and $y$ in turn is mapped to $z$ with $W(z)=w-5$ and so on and finally the low weight strings are mapped back to $x$. This is just an example of what I'm looking for.
Bijections that I'm not looking for:
-
Swaps. For example, say we choose $2^n/3$ vertices using some rule and call this the set $A$, which has $1/3$ of the total strings, but each $x\in A$ is mapped to a vertex where ones and zeros are flipped. So in this case, low weight strings are swapped with high weight strings but this is not what I'm looking for. I need a good mixing of strings of different weights.
-
Shifts. Say we choose all strings of a particular weight $w$ and call this the set $B$. Now say each $x\in B$ is mapped to $y\in B$ where $y$ is obtained from $x$ by shifting each bit of $x$ by a constant amount. This bijection clearly maps strings of weight $w$ to strings of weight $w$ and hence this is not what I'm looking for because again I 'm looking for a good mixing of strings of different weights.
Best Answer
Here is one approach which may or may not be what you're looking for:
Choose an arbitrary binary string to be the key. Then bit-wise xor with the key is a bijection.
More concretely, take a binary string $x$, and flip all the bits where the corresponding entry of the key is a 1. For instance, if $n=3$ and the key is $101$, then this bijection is "flip the first and the third bit".
If the weight of the key is even, then this bijection sends even-weighted strings to even-weighted strings, and vice versa. It can only change the weight by at most $W(\text{key})$. But if $W(\text{key})\approx \frac n2$, this shouldn't be too bad.