代码之家 › 专栏 › 技术社区 › Didier Trosset

除两个碱基外,是否存在灰色代码?

gray-code math

Didier Trosset · 技术社区 · 7 年前

只是好奇,是不是 Gray code 是否为基2以外的基定义?

我试图以3为基数进行计数,写下连续的值,注意只改变一个值。 特里特 一次。我已经能够列举出所有的值高达26(3**3-1),它似乎是有效的。

        000              122              200
        001              121              201
        002              120              202
        012              110              212
        011              111              211
        010              112              210
        020              102              220
        021              101              221
        022              100              222

我能看到的唯一问题是这三个 特里茨 循环回零时更改。但这只适用于奇数碱基。当使用偶数基时,循环回零只会改变一个数字,就像二进制那样。

我甚至认为它可以扩展到其他的基数,甚至十进制。当以10为基数计数时,这可能导致另一个排序…-)

    0  1  2  3  4  5  6  7  8  9 19 18 17 16 15 14 13 12 11 10
   20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30

现在的问题是,有人听说过吗?有申请吗?或者只是数学狂热?

2 回复 | 直到 15 年前

aioobe 15 年前

对。看看 Gray code article 在维基百科。上面有一个部分 n-ary Gray Code 。

有许多专门的灰色代码类型,除了二进制反射灰色代码。其中一种灰色代码是 N元灰色代码 也被称为 非布尔灰色代码 . 顾名思义,这种类型的灰色代码在编码中使用非布尔值。

Cory Engebretson 15 年前

为了完整性(Aioobe已经给出正确答案),这里有一个C++程序,列出了从00开始的所有168个2位格雷码的基础3,并标记了96个循环码。使用 algorithm from Wikipedia ,您可以轻松地为偶数基构造较长的灰色代码。对于不均匀的基底,可以更改程序以根据灰色代码生成。

使用此程序找到的第一个循环2位灰色代码是:

00 01 02 12 10 11 21 22 20

更改程序后,发现的第一个循环3位灰色为:

000 001 002 012 010 011 021 020 022 122 102 100 101 111
110 112 212 202 222 220 120 121 221 201 211 210 200

代码:

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

// Highest number using two trits
#define MAXN 9

int gray_code_count, cyclic_count;

bool changes_one_trit(int code1, int code2) {
  int trits_changed = 0;
  if ((code1 / 3) != (code2 / 3)) trits_changed++;
  if ((code1 % 3) != (code2 % 3)) trits_changed++;
  return (trits_changed == 1);
}

int generate_gray_code(int* code, int depth) {
  bool already_used;

  if (depth == MAXN) {
    for (int i = 0; i < MAXN; i++) {
      printf("%i%i ", code[i]/3, code[i]%3);
    }
    // check if cyclic
    if (changes_one_trit(code[MAXN-1], 0)) {
      printf("cyclic");
      cyclic_count++;
    }
    printf("\n");
    gray_code_count++;    
  }

  // Iterate through the codes that only change one trit
  for (int i = 0; i < MAXN; i++) {
    // Check if it was used already
    already_used = false;
    for (int j = 0; j < depth; j++) {
      if (code[j] == i) already_used = true;
    }
    if (already_used) continue;

    if (changes_one_trit(code[depth-1], i)) {
      code[depth] = i;
      generate_gray_code(code, depth + 1);
    }
  }
}

int main() {
  int* code = (int*)malloc(MAXN * sizeof(int));
  code[0] = 0;
  gray_code_count = 0;
  generate_gray_code(code, 1);
  printf("%i gray codes found, %i of them are cyclic\n", gray_code_count, cyclic_count);
  free(code);
}