I'm trying to figure why divide and conquer technique has this property:
for example, we count 0 to 7, then we divide them into 2 parts: [0, 2, 4, 6] and [1, 3, 5, 7]. Then we divide each of the 2 vectors into 2 parts again: [0, 4], [2, 6], [1, 5], [3, 7].
We surprisingly find that the binary of this order (0 4 2 6 1 5 3 7) is just symmetrical about (0 1 2 3 4 5 6 7):
0: 000 | 000:0
1: 001 | 100: 4
2: 010 | 010: 2
3: 011 | 110: 6
4: 100 | 001: 2
5: 101 | 101: 5
6: 110 | 011: 3
7: 111 | 111: 7
For even number of bits, it also holds. For example,
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
to
(0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)
0 : 0000 | 0000: 0
1 : 0001 | 1000: 8
2 : 0010 | 0100: 4
3 : 0011 | 1100: 12
4 : …. | ….
5 :
6 :
7 :
8 :
9 :
10:
11:
12:
13: …. | ….
14: 1110 | 0111: 7
15: 1111 | 1111: 15
I can partially understand it's because the property of divide and conquer, but is there any math equation for this kind of proof – i.e. proof of divide and conquer then reorder of a set of number is the bit symmetric of the original order, given set length = 2^n?
Best Answer
This would need to be formalized better, but anyway explains what is going on.
Let $n$ be the number of digits with which we represent any number $m$ such that $0 \le m \le 2^n-1$ (so in total $2^n$ representable numbers). The binary expansion of $m$ ($b_{n-1}b_{n-2}\ldots b_1b_0$) is:
$$m = \sum_{k=0}^{n-1} b_k2^k$$
We have a sequence of $2^n$ numbers $(0,1,2,\ldots,2^n-1)$ representable with the above equation ($(0,1,2,3,4,5,6,7)$ in your example, with $n=3$).
If we apply the "divide and conquer" that you propose, the sequence that we obtain in your example is $(0,2,4,6,1,3,5,7)$. To obtain that, we can multiply by $2$ the values in the original sequence and then compute the remainder modulo $7$. This is equivalent to adding $-7$ only for numbers on the original sequence that are greater or equal to $4$, which are the only ones that have $b_2 \not = 0$. Once that we discard the bits at position $3$ or more, subtracting $-7$ is equivalent to adding $1$ (see Two's complement), but we need to do this only for $m \ge 4$, therefore we can just add $b_2$, because it will be $0$ for $m < 4$. Summing up we start from the binary representation $b_2b_1b_0$, multiply by $2$ to get $b_2b_1b_00$, add $b_2$ to get $b_2b_1b_0b_2$, discard the most significant $b_2$ because on position $\ge 3$ to get $b_1b_0b_2$: we have moved $b_2$ to the least significant position.
In the next step we go from $(0,2,4,6,1,3,5,7)$ to $(0,4,2,6,1,5,3,7)$. We note that $b_2$ does not move anymore because we have $4$ even numbers followed by $4$ odd numbers before and after the permutation. If we make $\lfloor m/2 \rfloor$ of the numbers in $(0,2,4,6,1,3,5,7)$ and $(0,4,2,6,1,5,3,7)$ we get $(0,1,2,3,0,1,2,3)$ and $(0,2,1,3,0,2,1,3)$ respectively, therefore we are doing the same operation on the first and second half, working only on the two most significant bits $b_1b_0$ of $b_1b_0b_2$, and repeating the reasoning of the previous paragraph we can understand that we are swapping $b_1$ and $b_0$ to finally get $b_0b_1b_2$.
This can be extended to any number of digits $n$, for example for $n=4$ your sequence of operations is $\mathbf{b_3b_2b_1b_0}$, $\mathbf{b_2b_1b_0}b_3$, $\mathbf{b_1b_0}b_2b_3$, $b_0b_1b_2b_3$, where at each step you move and work on only the bold digits.