格雷碼（Gray Code）

說明

解法

實作：C    Java    Python    Scala    Ruby    JavaScript    Haskell

• C

#include <stdio.h> 
#include <stdlib.h> 

void doGray(int, void (*)(int*, int));
void init(int*, int);
int firstOneOf(int*, int);
void next(int*, int, int);
int isLast(int*, int);
void print(int*, int);

int main(void) { 
    int length;
    printf("輸入位元數："); 
    scanf("%d", &length); 

    doGray(length, print);
    
    return 0; 
} 

void doGray(int length, void (*take)(int*, int)) {
    int* gray = malloc(length * sizeof(int));
    init(gray, length);
    take(gray, length);
    int isOdd = 1; 
    while(!isLast(gray, length)) { 
        next(gray, length, isOdd);
        isOdd = 1 - isOdd;
        take(gray, length);
    }
    free(gray);
}

void init(int* gray, int length) {
    int i;
    for(i = 0; i < length; i++) { gray[i] = 0; } 
}

int firstOneOf(int* gray, int length) {
    int j;
    for(j = 0; gray[j] == 0; j++);
    return j;
}

void next(int* gray, int length, int isOdd) {
    int i = isOdd ? 0 : firstOneOf(gray, length) + 1;
    gray[i] = !gray[i];
}

int isLast(int* gray, int length) {
    int i;
    for(i = 0; i < length - 1; i++) if(gray[i]) { return 0; }
    return gray[i];
}

void print(int* gray, int length) {
    int j;
    for(j = length - 1; j >= 0; j--) { printf("%d", gray[j]); }
    printf("\n"); 
}

• Java

import java.util.*;

public class Gray {
    private int[] code;
    private boolean isOdd;
    public Gray(int[] code, boolean isOdd) {
        this.code = code; 
        this.isOdd = isOdd;
    }
    
    public int lastIndexOf(int elem) {
        int i;
        for(i = code.length - 1; code[i] != elem; i--);
        return i;
    }
    
    public Gray next() {
        int[] next = new int[0];
        int i = (isOdd ? code.length : lastIndexOf(1)) - 1;
        if(i != -1) {
            next = Arrays.copyOf(code, code.length);
            next[i] = 1 - next[i];
        }
        return new Gray(next, !isOdd);
    }
    
    public boolean isEmpty() { return code.length == 0; }

    public String toString() {
        return Arrays.toString(code) + (isOdd ? " odd" : " even");
    }
    
    public static List<Gray> gray(int length) {
        List<Gray> grays = new ArrayList<>();
        Gray gray = new Gray(new int[4], true);
        do { grays.add(gray); } while(!(gray = gray.next()).isEmpty());
        return grays;
    }

    public static void main(String[] args) {
        for(Gray gray : gray(4)) { System.out.println(gray); }
    }
}

• Python

class Gray:
    def __init__(self, code, isOdd):
        self.code = code
        self.isOdd = isOdd
        
    def lastIndexOf(self, elem):
        return len(self.code) - 1 - self.code[::-1].index(elem)
    
    def next(self):
        i = (len(self.code) if self.isOdd 
                            else self.lastIndexOf(1)) - 1
        return Gray(
            [] if i == -1 \
               else self.code[0:i] + [1 - self.code[i]] + self.code[i + 1:],
               not self.isOdd)
    
    def isEmpty(self):
        return len(self.code) == 0
               
    def __str__(self):
        return str(self.code) + (' odd' if self.isOdd else ' even')
        
def gray(length):
    def successors(gray):
        nx = gray.next()
        return [] if nx.isEmpty() else [nx] + successors(nx)
            
    init = Gray([0] * length, True)
    return [init] + successors(init)
    
for code in gray(4):
    print(code)

• Scala

class Gray(code: List[Int], isOdd: Boolean) {
    def next = {
        val i = (if(isOdd) code.size else code.lastIndexOf(1)) - 1
        new Gray(
            if(i == -1) Nil
            else code.take(i) ++ 
             ((1 - code(i)) :: code.drop(i + 1)), !isOdd)
    }
    def isEmpty = code.isEmpty
    override def toString = 
        code.toString.replace("List", if(isOdd) "Odd  " else "Even ")
}

def gray(length: Int) = {
    def successors(gray: Gray): List[Gray] = {
        val nx = gray.next
        if(nx.isEmpty) Nil else nx :: successors(nx)
    }
    
    val init = new Gray((for(i <- 0 until length) yield 0).toList, true)
    init :: successors(init)
}

gray(4).foreach(println)

• Ruby

class Gray
    def initialize(code, isOdd)
        @code = code
        @isOdd = isOdd
    end
    
    def next
        i = @isOdd ? @code.size - 1 : @code.rindex(1) - 1
        Gray.new(i == -1 ? [] : 
            @code.take(i) + [1 - @code[i]] + @code.drop(i + 1), !@isOdd)
    end
    
    def empty?
        @code.empty?
    end
    
    def to_s
        "#{@code.to_s + (@isOdd ? ' odd' : ' even')}"
    end
end
        
def gray(length)
    successors = ->(gray) {
        nx = gray.next
        nx.empty? ? [] : [nx] + successors.call(nx)
    }
            
    init = Gray.new([0] * length, true)
    [init] + successors.call(init)
end
    
gray(4).each do |code|
    print("#{code}\n")
end

• JavaScript
  

function Gray(code, isOdd) {
    this.code = code;
    this.isOdd = isOdd;
}

Gray.prototype.toString = function() {
    return this.code + (this.isOdd ? ' odd' : ' even');
};

Gray.prototype.next = function() {
    var i = (this.isOdd ? this.code.length : this.code.lastIndexOf(1)) - 1;
    return new Gray(i === -1 ? [] : 
               this.code.slice(0, i)
                        .concat([1 - this.code[i]])
                        .concat(this.code.slice(
                            i + 1, this.code.length)), 
           !this.isOdd);
};

function gray(length) {
    function successors(gray) {
        var nx = gray.next();
        return nx.code.length === 0 ? [] : [nx].concat(successors(nx));
    }
    var init = new Gray(new Array(length + 1)
                                .join(0)
                                .split('')
                                .map(function() {return 0;}), 
               true);
    return [init].concat(successors(init));
}

gray(4).forEach(function(code) {
    alert(code);
});

• Haskell

data Code = Gray [Int] Bool

instance Show Code where
    show (Gray code isOdd) = 
        show code ++ if isOdd then " odd" else " even"

lastIndexOfOne code =
    if last code == 1 then length code - 1
    else lastIndexOfOne \$ init code
    
succ' (Gray digits isOdd) =
    let i = if isOdd then length digits - 1
            else lastIndexOfOne digits - 1
    in Gray (next digits i) (not isOdd)
    where 
        next digits i =
            if i == -1 then []
            else take i digits ++ 
                 ((1 - digits !! i) : drop (i + 1) digits)

gray length =
    let hd = Gray (replicate length 0) (True)
    in hd : successors hd
    where
        successors gray@(Gray digits isOdd) =
            let nx@(Gray code _) = succ' gray
            in if code == [] then []
               else nx : (successors nx)
               
main = sequence [print code | code <- gray 4]