How can I use algebraical properties of group operations for generating subsets of blocks of binary numbers of same population count?

Question

Considering blocks of binary digits, are from all binary numbers $\in \{0,\cdots,2^{N}-1\}$

Which operations can I define which will preserve the number of 1-bits in any given number? Is there some systematical way to construct a set or family of such operations which will make me able to systematically create all numbers given one particular number?

What I am interested in are all numbers of a particular population count $k$, or bit-sum if you will.

---

Own work:

Consider one number for $k=1, N = 4$ : 0001

Rotation of the bits will preserve the sum of digits. This in algebraic language can be viewed as cyclic groups. For this example in group theoretical language we can prove that we can generate all possible 4 bit numbers of sum 1.

But what happens for $k=2$, starting with for example 0011? Rotations can give us (generate) 0110, 1100, 1001, but these are only a subset of all possible 4 bit numbers which digit sum is 2.

We also need to be able to make 0101 and 1010.

Permutation of first and last bit takes 0011 $\to$ 1010 and with a combination of these two operations we can now generate all two-summing binary numbers of length 4.

But what about a general case? Can we prove that the combination of these two operations and any number for any $k,N$ will always be able to generate all numbers in the same set? If it is not possible, what will be a more fruitful approach?

Answer 1

Yes, your two operations allow you to generate all numbers with $k$ bits, starting from any particular number with $k$ bits.

Think of the bits as being arranged in a circle. The first and last bits are adjacent to each other on the circle, and you are able to swap those two adjacent bits. Furthermore, with the help of the rotation operation, you can swap any two adjacent bits. Just rotate all of the bits until the two bits you want to swap occupy the spots of the first and last bits, then perform the swap, then rotate everything so the two bits are back in the same two positions (but swapped).

It is well known that if you can swap any two adjacent elements, then you can achieve any permutation. https://proofwiki.org/wiki/Transpositions_of_Adjacent_Elements_generate_Symmetric_Group Since you can permute the bits arbitrarily, you can get all numbers with $k$ bits.

Answer 2

There are other ways of generating all $k-$weight strings of length $n.$ This is equivalent to generating all $k-$combinations (subsets of cardinality $k$) of an $n-$set. One particularly easy one is lexicographic generation. It can be written in a simple to understand algorithm. Let's denote the $n-$ set by $\{0,1,\ldots,n-1\}$ and let the current elements in the $k-$ subset be denoted $c_k,c_{k-1},\ldots,c_1.$ For simplicity I will write out the case $k=3$ the general case is similar. We start with the lexicographically smallest set which is supported on $\{0,1,2\}.$ $$ for~c_3=2,3,\ldots,n-1~do\\ \quad for~c_2=1,2,\ldots,c_3-1~do\\ \quad \quad for~c_1=0,1,\ldots,c_2-1~do\\ \quad\quad output~ \{c_3,c_2,c_1\}\\ end ~for;~end for; ~end for;\\ $$ Running this with $n=6,$ and $k=3,$ and representing the set ${c_3,c_2,c_1}$ simply by the $3-$tuple $c_3c_2c_1$ gives the following subsets in order: $$ 210,310,320,321,410,420,421,430,431,432,510,520,521,530,531,532,540,541,542,543 $$

Another one is called revolving door order, a bit more complicated to represent but you can find it online, for example at http://people.math.sfu.ca/~kya17/teaching/math343/15-343.pdf