6

只是好奇，格雷码是否为基数二以外的基数定义？

我试着以 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

我能看到的唯一问题是，当循环回零时，所有三个trit 都会发生变化。但这仅适用于奇数碱基。当使用偶数基时，循环回零只会改变一个数字，如二进制。

我什至猜想它可以扩展到其他基础，甚至是十进制。在以十为底数时，这可能会导致另一个排序... :-)

    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

现在的问题是，有人听说过吗？有申请吗？还是只是数学狂潮？

4

2 回答 2

10

是的。查看 wikipedia 上的格雷码文章。它有一个关于n-ary Gray Code的部分。

除了二进制反射格雷码之外，还有许多特殊类型的格雷码。一种这样的格雷码是n 元格雷码，也称为非布尔格雷码。顾名思义，这种类型的格雷码在其编码中使用非布尔值。

于 2010-10-01T09:43:22.670 回答
4

只是为了完整性（因为 aioobe 已经给出了正确的答案），这是一个 C++ 程序，它列出了所有 168 个以 00 开头的基数为 3 的 2 位格雷码，并标记了 96 个循环的。使用来自 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);
}
于 2010-10-01T10:02:58.763 回答