0

有一个很好的解决方案：使用 itertools 的格雷码顺序的笛卡尔积？，有没有办法给这个解决方案添加一些简单的东西，以报告从一个元素到格雷码顺序的笛卡尔积的下一个元素发生变化的集合（它的索引）？也就是说， agray_code_product_with_change(['a','b','c'], [0,1], ['x','y'])会产生如下内容：

(('a',0,'x'), -1)
(('a',0,'y'), 2)
(('a',1,'y'), 1)
(('a',1,'x'), 2)
(('b',1,'x'), 0)
(('b',1,'y'), 2)
(('b',0,'y'), 1)
(('b',0,'x'), 2)
(('c',0,'x'), 0)
(('c',0,'y'), 2)
(('c',1,'y'), 1)
(('c',1,'x'), 2)

我想避免采用连续元组之间的“差异”，但要进行恒定时间更新——因此要从格雷码顺序开始。一种解决方案可能是编写一个index_changed迭代器，即返回index_changed(3,2,2)我想要的序列-1,2,1,2,0,2,1,2,0,2,1,2，但是可以将更简单的东西添加到上面的解决方案中以获得相同的结果吗？

4

1 回答 1

0

这个问题有几个问题，但我会保持这样，而不是仅仅通过把它变成一个“变色龙问题”来让它变得更糟

确实，当您有这个“索引更改”序列时，为什么还要按格雷码顺序询问笛卡尔积的元素呢？所以我想我真正想要的是这个序列的有效计算。所以我最终实现了上面提到的gray_code_product_with_change，它采用一组基本集合，例如，['a','b','c'], [0,1], ['x','y']计算这个“索引更改”序列，并在它通过序列时更新这个基本集合集。由于实现最终比我想象的更有趣，我想我会分享，如果有人觉得它有用：

（免责声明：可能不是最 Pythonic 的代码，而几乎是 C 语言）

def gray_code_product_with_change(*args, repeat=1) :

    sets = args * repeat
    s = [len(x) - 1 for x in sets]
    n = len(s)

    # setup parity array and first combination
    p = n * [True] # True: move foward (False: move backward)
    c = n * [0] # inital combo: all 0's (first element of each set)

    # emit the first combination
    yield tuple(sets[i][x] for i, x in enumerate(c))

    # incrementally update combination in Gray code order
    has_next = True
    while has_next :

        # look for the smallest index to increment/decrement
        has_next = False
        for j in range(n-1,-1,-1) :

            if p[j] : # currently moving forward..

                if c[j] < s[j] :
                    c[j] += 1
                    has_next = True

                    # emit affected set (forward direction)
                    yield j

            else : # ..moving backward

                if c[j] > 0 :
                    c[j] -= 1
                    has_next = True

                    # emit affected set (reverse direction)
                    yield -j

            # we did manage to increment/decrement at position j..
            if has_next :

                # emit the combination
                yield tuple(sets[i][x] for i, x in enumerate(c))

                for q in range(n-1,j,-1) : # cascade
                    p[q] = not p[q]

                break

试图在计算这个序列时尽可能多地梳理出性能——因为一组集合的笛卡尔积中的元素数量随着集合的数量（大小为 2 或更多）呈指数增长——我在 C 中实现了这个。它本质上是实现上面提到的index_changed（使用稍微不同的符号）：

（免责声明：这里有很大的优化空间）

void gray_code_sequence(int s[], int n) {

  // set up parity array
  int p[n];
  for(int i = 0; i < n; ++i) {
    p[i] = 1; // 1: move forward, (1: move backward)
  }

  // initialize / emit first combination
  int c[n];
  printf("(");
  for(int i = 0; i < n-1; ++i) {
    c[i] = 0; // initial combo: all 0s (first element of each set)
    printf("%d, ", c[i]); // emit the first combination    
  }
  c[n-1] = 0;
  printf("%d)\n", c[n-1]);

  int has_next = 1;
  while(has_next) {

    // look for the smallest index to increment/decrement
    has_next = 0;
    for(int j = n-1; j >= 0; --j) {

      if(p[j] > 0) { // currently moving forward..

        if(c[j] < s[j]) {
          c[j] += 1;
          has_next = 1;

          printf("%d\n", j);
        }
      }

      else { // ..moving backward

        if(c[j] > 0) {
          c[j] -= 1;
          has_next = 1;

          printf("%d\n", -j);
        }
      }

      if(has_next) {

        for(int q = n-1; q > j; --q) {
          p[q] = -1 * p[q]; // cascade
        }

        break;
      }
    }
  }
}

与上面的python相比（其中笛卡尔积的元素的屈服被抑制，并且只有序列的元素被屈服，因此输出基本相同，为了公平比较），这个C实现似乎渐近地快大约 15 倍。

再一次，这个 C 代码可以被高度优化（讽刺的是，python 代码是如此像 C 的，这是众所周知的），例如，这个奇偶校验数组可以存储在单一int类型中，执行位移>>操作等，所以我敢打赌甚至可以实现 30 或 40 倍的加速。

于 2020-05-02T15:55:47.540 回答