Is there any direct approach to generate discrete 2 partitions of a set of having 2^n elements for a given n ?

Question

Assume that you have a set S of having 2^2 elements first, let S={0,1,2,3} Then the desired 2 partitions would be 1-{{0,1},{2,3}} 2-{{0,2},{1,3}} 3-{{0,3},{1,2}}

If S={0,1,2,3,4,5,6,7} having 2^3 elements then similarly the 2 partitions would be

1- {{0,1},{2,3},{4,5},{6,7}} 2- {{0,2},{1,3},{4,6},{5,7}} 3- {{0,3},{1,5},{2,6},{4,7}} 4- {{0,4},{1,6},{2,5},{3,7}} 5- {{0,5},{1,4},{2,7},{3,6}} 6- {{0,6},{1,7},{2,4},{3,5}} 7- {{0,7},{1,2},{3,4},{5,6}}

So it seems that for S having 2^n elements the initial table would like

1: {{0,1},{2,3},{4,5},{6,7},...,{(2^n)-2,(2^n)-1}} 2: {{0,2},... } . . . (2^n)-1: {{0,(2^n)-1},... }

I am just wondering whether there is an direct approach to generate the above table for a given n.

Thanks

Answer 1

I presume you want $2^n-1$ partitions of ${0,\ldots,2^n-1\}$ into parts of size two so that each possible pair occurs exactly once in a partition. You can do this as follows. Write the numbers in question base $2$. Then each can be represented by $n$ binary digits going from $00\cdots0$ to $11\cdots 1$. Define an operation $\oplus$ on these as follows: we obtain $a\oplus b$ by add corresponding digits in $a$ and $b$ modulo $2$. For example $11\oplus 14=5$ as in base $2$, $11$ and $14$ are $1011$ and $1110$, and $1+1$ is $0$ mod $2$, $0+1$ is $1$ mod $2$, $1+1$ is $0$ mod $2$ and $1+0$ is $1$ mod $2$ so in binary $a\oplus b$ is $0101$ which is $5$. The operation $\oplus$ is sometimes known as "nim addition" as it is used in the analysis of the game nim.

To get the $j$-th partition where $1\le j\le 2^n-1$ we just pair off $a$ and $a\oplus j$. So for $n=4$, the partition for $j=5$ is $\{ \{0,5 \}, \{1,4 \}, \{2,7 \}, \{3,6 \}, \{8,13 \}, \{9,12 \}, \{10,15 \}, \{11,14 \} \}$ as $0\oplus 5=5$, $1\oplus 5=4$, $2\oplus 5=7$ etc.