Gray Code (Self Doubt)

Question

Was solving the GO 2019 pdf when I encountered this question asked in TIFR 2017. Although I have understood this question, I have one doubt-

It is mentioned in the question that for a 3-bit number, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is one of the possible Gray codes.

Then, how many such orders are there for an n-bit number? 

Comments

2^n

---

Can you please explain how the number of such orders will be $2^{n}$. According to this, no. of possible orders for a 1-bit number should be $2^{1} = 2$. However, I think only $1$ such order is possible, which is $\left ( 0, 1 \right )$.

---

using 1 bit we can have 0 ,1 . i.e. $2^1$ = $2$ representation

using 2 bits we can have 00 , 01 , 10 , 11 i.e. $2^{2}$ representation

using 3 bits we can have 000,001,011,010,110,111,101,100 i.e. i.e. $2^{3}$ representation

---

I think you might have misunderstood my question. I was not asking about how many different such n-bit numbers are possible. Rather, I was asking how many orderings of such n-bit numbers are possible.

For example, for 2-bit no., the possible orders are (00, 01, 11, 10) and (00, 10, 11, 01). Therefore, there are 2 such orders for 2-bit numbers.

---

yes i misunderstood,

but using only 1 bit we can have {1,0} and {0,1} both right ? since the bits are differing by only 1 bit so 2 ordering.

---

if you apply constraint that all the bits in 1st word should be 0 then it will be 1 ordering for ordering possible using 1 bit rght ?

---

But, aren't we just rotating the numbers by 1 place when we consider the orderings (0, 1) and (1, 0) to be different.

On the other hand, (00, 01, 11, 10) and (00, 10, 11, 01) are distinct orderings.

---

yes that is what i am asking

i am saying they are different ordering because

if x and y are 2 consecutive decimal numbers

case 1. then we can represent x using 0 and y using 1 in gray code.

case 2. then we can represent x using 1 and y using 0 in gray code.

here both the cases satisfies property of gray code representation

i.e. 2 ordering possible to represent the numbers x and y in gray code using only 1 binary bit.

---

I am not taking any constraint as such but orderings are (00, 01, 11, 10), (01, 11, 10, 00), (11, 10, 00, 01) and (10, 00, 01, 11) are not exactly different in the sense that they are just rotating the numbers by 1 place. 

On the other hand, as I said earlier (00, 01, 11, 10) and (00, 10, 11, 01) are distinct orderings.

Also, for 3-bit numbers, I kind tried to find the no. of possible orders by brute-force method.  I came up with the following orderings till now-

1. (000, 001, 011, 010, 110, 111, 101, 100),
2. (000, 001, 011, 010, 110, 100, 101, 111),
3. (000, 001, 011, 111, 101, 100, 110, 010),
4. (000, 001, 101, 100, 110, 111, 011, 010),
5. (000, 001, 101, 100, 110, 010, 011, 111),
6. (000, 001, 101, 111, 011, 010, 110, 100),
7. (000, 010, 110, 100, 101, 111, 011, 001),
8. (000, 010, 011, 001, 101, 111, 110, 100),
9. (000, 100, 110, 010, 011, 111, 101, 001),
10. ...

If I am not mistaken, I already have 9 orderings for 3-bit numbers.

---

Ok so you want to say that ABC , CBA, BCA should be counted as one bcoz they are just rotating the numbers by 1 place right ?

---

Yes.

---

I kind of have a vague idea about how to proceed to solve this problem, although I am not quite sure if it is correct or not-

I was thinking about the n-variable K-Map that we can have for any n-bit number.

Suppose, we take the 2 variable K-Map. Then, no. of such possible orderings could be found out by finding the no. of paths that we can take starting from the cell(0,0), then traversing through all the cells and finally returning back to the initial cell(0,0).

Here, we need to keep in mind that from any cell i, we can only go to any one of the horizontally or vertically adjacent cells next as those are the only cells that would differ from cell i by 1 bit. Also, we need to keep in mind the wrap around property of the K-Map (e.g. cell(000) and cell(010) are adjacent in case of 3-variable K-Map).

---

it sounds correct.

In this problem we have 2 constraints,

1. each consecutive representation should differ by 1 bit only.
2. all the circular rotations possible for a sequence of representations is counted as 1.

---

therefore here we have to find the number of circular permutations of grey codes possible using n-bit.

here the solution would be to generate a recurrence relation and then solve it to get the answer.

---

I further tried to reduce this to a graph theory problem-

I considered the cells as nodes drew an edge between the nodes if they were adjacent (i.e. differed by 1 bit). Then the problem basically reduced to finding the no. of cycles from the node representing cell (0,0) (say, the origin) that pass through each vertex exactly once, i.e. finding the no. of distinct directed Hamiltonian cycles.

Am I correct in proceeding as such? Further, is there any formula to find the no. of distinct directed Hamiltonian cycles for any arbitrary graph?

---

It will look like this and we have to find hamiltonian cycles possible right ?

assume $\rightarrow$ is bidirectional

 

---

I don't think there should be an edge between node(01) and node (10) as they differ by 2 bits.

---

like this right ?

---

Yes, this one is correct.

---

So, if I am not mistaken, the problem reduces to finding the no. of distinct directed Hamiltonian cycles for such a graph where nodes (that represent the Gray codes) have an edge between them only if they differ by 1-bit position.

---

Yes just 1 mistake

we have to find hamiltonian paths and not hamiltonian cycles

In the above graph there is only 1 cycle possible starting from 00 i.e. 00-01-11-10-00 and all other cycles are just its rotation.

but there are 2 hamiltonian paths starting from 00 i.e. 00-01-11-10 or 00-10-11-01

---

every time the hamiltonian paths will be different right , there is not any general formula ?

we can't generalize it as it will vary from graph to graph

$\therefore$ we have to do it by brute force technique if we are using graph method.

---

Yeah, you are right. Here, we are trying to find the no. of Hamiltonian paths and not Hamiltonian cycles. Also, such graphs are actually a special type of graphs called Hypercubes (somehow I completely forgot about them 😅). Also, finding the no. of Hamiltonian paths in an arbitrary graph is an np-complete problem. So, no other option apart from brute-force.

---

I think hamiltonian cycles also correct if we consider undirected edges. Isn't it?

---

No, the problem reduces to finding the no. of different Hamiltonian paths. For example, if we consider a 1-bit no., the hypercube will be a simple edge connecting two nodes (i.e. no cycles).

Answer 1

If we model as hypercube then we can convert it to bipartite graph. And from bipartite graph we can get number of hamiltonian cycles. For 3-bit,

V1                                       V2

000 (4-possibilities)        001(3-possibilities)

011  (3-possibilities)        111 (2)

101 (2)                                100(1)

110(1)                                 010(1)

 

Total = 4*3*3*2*2 =144 but as they are cycles divide by 2. So total = 72.

Please let me know if there is any wrong wit this method.

Comments

What do the possibilities represent?

---

It represents the no. Of ways it can connect to vertices in other set. If we want hamiltonian cycles, we can work out in this way.

---

How does the node (000) connect to 4 vertices in the other set. The hypercube for 3-digit no. is a cube and each node k connects to only 3 other nodes. This is because there are only 3 other nodes that differ from the node k by a single bit position.

Also, in the bipartite graph, node (000) won't have an edge to node (111).

---

Yes you are right. Need to it is three possibilities only for each node. Thanks for pointing this.

Answer 2

we have a unique gray code for each binary combination which is obtained by Exoring in some manner,

since we have 2^n binary combinations for n-bits similarly,we have 2^n combinations of gray code for n-bits