グレイコードの出力

Python, 30分プログラム | 21:13 |

30分プログラム、その627。anarchy golf - Gray code via 2009-05-29 - id:anatooの大冒険 ?力への意思? - sideportをやってみる。

最初は、2進数をずらずらと並べればいいと思ってたけれども、グレイコード - Wikipediaを読むとどうもそうではないらしい。

細かいことはよくわからなかったけれども、とりあえずv ^ (v >> 1)で生成できるらしいよ。

もともとはGOLFの問題だけど、そこにはこだわらない方向で。

使い方

$ python graycode.py
000
001
011
010
110
111
101
100

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# graycode.py -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/07/27 20:50:19
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

def to_graycode(v):
    return v ^ (v >> 1)

def str_binary(n):
    if n <= 1:
        yield str(n)
    else:
        for i in str_binary(n/2):
            yield i
        yield str(n%2)

def padding(width,char,n):
    l = len(n)
    if l >= width:
        return n
    else:
        return char * (width - l) + n

def graycode(n_bits):
    for v in xrange(0,2**n_bits):
        yield padding(n_bits,
                      '0',
                      "".join(str_binary(to_graycode(v))))

for g in graycode(3):
    print g

参考

• 過去の30分プログラム
• グレイコード - Wikipedia