Computer a Gray code


#1

Hi:

In the Python book 15.10 computing a Gray code, I am thinking whether it is necessary to add three lines of codes after

if directed_gray_code(history):
return True

so it becomes:

if directed_gray_code(history):
return True
else:
del(result[-1])
history.remove(candidate_next_code)

This is because if you have checked that the recursively called function returns False, it means at the end of the day, the first and last element will not satisfy the requirement, so the candidate is not valid to be added. Rather, you need to try other candidate in the for loop, and you need to clear what was done in the previous round.

I know that as a result, the original code also outputs the correct answer. This is because in fact, the first-last element check alway passes. But logically, I think it is necessary to add the lines of codes.

Am I correct?

Thanks.


#2

Hi @helloworld,

I think you are right. Logically it shall add those lines for sure, and the reasoning is what you said. One reason why our code works is because the gray code is unique if we forget the permutation of sequence.

This is great question, and thanks for this!


#3

Thanks a lot @tsunghsienlee for your answer and explanation!