Assignment 3

Think of the following situation. There is an empty room, and s persons are standing outside the room. Then you repeat a sequence of steps. At each step either one person enters the room or one person leaves the room (but not both). Your task is to find a sequence of steps such that every possible combination of the s persons is present in the room once and only once.

This problem can be solved by using Gray codes. An s-bit Gray code is a sequence C₀,C₁,..., C_2^s-1, where each C_i is a sequence of exactly s bits, and where each C_i differs from the previous code C_i-1 in exactly one bit position. Here is an example of a 4-bit Gray code:

   0000
   0001
   0011
   0010
   0110
   0111
   0101
   0100
   1100
   1101
   1111
   1110
   1010
   1011
   1001
   1000

In order to translate our problem to Gray codes, let us number the persons by integers between 0 and s-1. Consider a particular point of time. If person i is inside the room at that time, set Bit_i=1, else set Bit_i=0. The configuration of the room at that time is represented compactly by the s-bit code Bit_s-1Bit_s-2...Bit₁Bit₀.

Suppose s = 4. Initially all persons are outside the room, so the configuration of the room is 0000. Then Person 0 enters the room, and the configuration changes to 0001. In the next step, Person 1 enters the room changing the configuration to 0011. Then Person 0 leaves the room and the configuration becomes 0010. This corresponds to the first four lines of the above Gray code.

Gray codes can be constructed for any length. Let me first supply an inductive procedure for the construction. The Gray code of length 1 is the following sequence:

   0
   1

Now suppose that C₀, C₁, ..., C_2^s-1 is the Gray code of length s. Then the Gray code of length s+1 is constructed as: 0C₀, 0C₁, ..., 0C_2^s-1, 1C_2^s-1, ..., 1C₁, 1C₀. Clearly, the constructed sequence satisfies the desired properties.

In this exercise, we ask you to generate Gray codes iteratively. Suppose you want to construct the s-bit code C₀,C₁,...C_2^s-1. Each C_i differs from the previous code C_i-1 in exactly one bit position. Denote this position by pos(i). It turns out that pos(i) is the non-negative integer k for which 2^k divides i but 2^k+1 does not. The following table illustrates this construction.

i	k = pos(i)	Ci	Action	Persons inside room	Persons outside room
0		0000		_	3,2,1,0
1	0	0001	Person 0 enters room	0	3,2,1
2	1	0011	Person 1 enters room	1,0	3,2
3	0	0010	Person 0 leaves room	1	3,2,0
4	2	0110	Person 2 enters room	2,1	3,0
5	0	0111	Person 0 enters room	2,1,0	3
6	1	0101	Person 1 leaves room	2,0	3,1
7	0	0100	Person 0 leaves room	2	3,1,0
8	3	1100	Person 3 enters room	3,2	1,0
9	0	1101	Person 0 enters room	3,2,0	1
10	1	1111	Person 1 enters room	3,2,1,0	_
11	0	1110	Person 0 leaves room	3,2,1	0
12	2	1010	Person 2 leaves room	3,1	2,0
13	0	1011	Person 0 enters room	3,1,0	2
14	1	1001	Person 1 leaves room	3,0	2,1
15	0	1000	Person 0 leaves room	3	2,1,0

Write a program that reads the number s of persons and prints the sequence of steps (persons entering and leaving the room) so as to achieve your goal of having each combination in the room once and only once. Proceed as follows:

• Write a function that, given a positive integer i, returns the non-negative integer k such that 2^k divides i but 2^k+1 does not. The integer k is called the multiplicity of 2 in i.

• Write a function that given a code and a bit position, flips the bit of the code at the given position.

• Write a function that prints a configuration of the room as a sequence of s bits.

• Write the main() function that calls the above functions to solve your problem.

Report the output of your program for s = 8 persons.

Sample output

   How many persons? 4
   i =   0,                              code = 0000, Persons inside :
   i =   1, k = 0, Person 0 enters room, code = 0001, Persons inside : 0
   i =   2, k = 1, Person 1 enters room, code = 0011, Persons inside : 10
   i =   3, k = 0, Person 0 leaves room, code = 0010, Persons inside : 1
   i =   4, k = 2, Person 2 enters room, code = 0110, Persons inside : 21
   i =   5, k = 0, Person 0 enters room, code = 0111, Persons inside : 210
   i =   6, k = 1, Person 1 leaves room, code = 0101, Persons inside : 20
   i =   7, k = 0, Person 0 leaves room, code = 0100, Persons inside : 2
   i =   8, k = 3, Person 3 enters room, code = 1100, Persons inside : 32
   i =   9, k = 0, Person 0 enters room, code = 1101, Persons inside : 320
   i =  10, k = 1, Person 1 enters room, code = 1111, Persons inside : 3210
   i =  11, k = 0, Person 0 leaves room, code = 1110, Persons inside : 321
   i =  12, k = 2, Person 2 leaves room, code = 1010, Persons inside : 31
   i =  13, k = 0, Person 0 enters room, code = 1011, Persons inside : 310
   i =  14, k = 1, Person 1 leaves room, code = 1001, Persons inside : 30
   i =  15, k = 0, Person 0 leaves room, code = 1000, Persons inside : 3

Notes

• Represent each code by an unsigned integer.

• In order to check whether the k-th bit of code is one, it suffices to compute the bit-wise AND of code with 2^k.

• The k-th bit of code can be flipped by bit-wise XOR of code with 2^k.

• You may use the following array for storing powers of 2.

     const unsigned long bitPos[32] = {
        0x00000001, 0x00000002, 0x00000004, 0x00000008,
        0x00000010, 0x00000020, 0x00000040, 0x00000080,
        0x00000100, 0x00000200, 0x00000400, 0x00000800,
        0x00001000, 0x00002000, 0x00004000, 0x00008000,
        0x00010000, 0x00020000, 0x00040000, 0x00080000,
        0x00100000, 0x00200000, 0x00400000, 0x00800000,
        0x01000000, 0x02000000, 0x04000000, 0x08000000,
        0x10000000, 0x20000000, 0x40000000, 0x80000000
     };
  

---

[Submission site] [Lab home] [Course home]