2
$\begingroup$

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows.

You start with an empty room and a group of n people waiting outside. At each step, you may either admit one person into the room, or let one out. Please design an algorithm which generates a sequence of $2^n − 1$ steps, so that every possible combination of people is achieved exactly once. For example, for $n = 3$, one possible sequence would be

$\qquad\displaystyle e_1, e_2, x_1, e_3, e_1, x_2, x_1$.

where $e_i$ means person $i$ enters the room and $x_j$ means person $j$ exits the room

Hint: study the Hanoi Tower algorithm.

In my research on the prompt, I've found many people referencing Gray Code, but I don't understand how to implement it in an algorithm to compute this combination. I also found a very similar problem, but there wasn't an actual implementation of it.

It would be greatly appreciated if you could point me in the right direction on where to go with this algorithm.

$\endgroup$
  • $\begingroup$ Assume you have a sequence that does what you want for $n$ people. Can you use it to get one for $n+1$ people? Or, going the route of Gray code: do you understand you Gray codes are an answer? The Wikipedia article contains code examples. $\endgroup$ – Raphael Feb 24 '15 at 14:53
  • $\begingroup$ I understand your hint fully, I've done recursion problems before, but I'm struggling with the implementation. For example, what would be the best way to store whether or not a user is in the room? I'm looking for a bit more of an actual example of how to do it, not just theoretical hints. $\endgroup$ – jroschen Feb 24 '15 at 15:19
  • $\begingroup$ In that case, I recommend you outline your algorithmic idea in the question. (If actual programming is your issue, Stack Overflow is the place to go.) $\endgroup$ – Raphael Feb 24 '15 at 15:27
1
$\begingroup$

Base case It's easy to generate the combinations when $n=1$: just use the operation $e_1$.

Recursion Now assume that you have a sequence $ops_n$ that will generate all the combinations of $n$ people. Define $rops_n$ to be the sequence of operations that "undoes" $ops_n$, namely first form the reverse of $ops_n$ and then replace all "enter" operations with "leave" operations and vice versa. For example, if $ops_2 = \langle\, e_1, e_2, x_1\,\rangle$, then $rops_n =\langle\, e_1, x_2, x_1\,\rangle$. It's not difficult to see that $ops_n, rops_n$ will generate all the combinations of $n$ people and then produce the same combinations in reverse order.

Finally, show that if $ops_n$ generates all the $n$-combinations, then the sequence $ops_n, e_{n+1}, rops_n$ will generate all the $(n+1)$-combinations: first all the ones without person $n+1$ and then all the ones with person $n+1$. From this construction it's clear inductively that you can generate all $n$ combinations with $2^n-1$ operations.


As per the hint you were given, this is very similar in spirit to the Towers of Hanoi problem: To move $n+1$ disks from peg 1 to peg 2, you first move $n$ disks from peg 1 to peg 3, then move the largest disk to peg 2, and finally move the $n$ disks on peg 3 to peg 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.