FilesExpand file tree

 master

/

grey_code.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

57 lines (44 loc) · 1.4 KB

 master

/

grey_code.py

Top

File metadata and controls

• Code
• Blame

57 lines (44 loc) · 1.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

#!/usr/bin/env python

'''

Leetcode: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0

01 - 1

11 - 3

10 - 2

Note:

For a given n, a gray code sequence is not uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

http://www.matrix67.com/blog/archives/266

n-th gray code: n xor (n >> 1)

'''

from __future__ import division

import random

def print_int(codes):

for c in codes:

print c, '-', int(c,2)

def gray_code(n):

if n == 1: return ['0','1']

prev_codes = grey_code(n-1)

codes = []

for c in prev_codes:

codes.append('0'+c)

for c in reversed(prev_codes):

codes.append('1'+c)

return codes

def gray_code_iter(n):

codes = ['0','1']

for i in range(1,n):

new_codes = ['0'+c for c in codes] + \

['1'+c for c in reversed(codes)]

codes = new_codes

return codes

def gray_code_bit(n):

ret = []

count = 1 << n;

for i in range(count):

ret.append( bin(i ^ (i >> 1)) )

return ret

if __name__ == '__main__':

print_int(gray_code_bit(3))

print_int(gray_code_iter(3))