グレイコードの出力

Python 30分プログラム

30分プログラム、その627。anarchy golf - Gray code via はてなグループをやってみる。
最初は、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

参考