格雷码顺序的笛卡尔积：在此顺序中包括受影响的集合？

Question

有一个很好的解决方案：，有没有办法向这个解决方案添加一些简单的东西来报告集合（它的索引）经历了从一个元素到下一个元素的变化格雷码阶的笛卡尔积？也就是说，gray_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)

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

Answer 1

这个问题有几个问题，但我会保持这样，而不是把它变成一个 "chameleon question"

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

（免责声明：可能不是最 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相比（这里抑制了笛卡尔积的元素的产生，只产生了序列的元素，所以输出本质上是一样的，对于a公平比较），这个 C 实现似乎快了 15 倍，渐近地。

同样，这个 C 代码可以被高度优化（具有讽刺意味的是 python 代码是如此的像 C 一样被人们熟知），例如，这个奇偶校验数组可以存储在一个 int类型，执行移位 >> 操作，等，所以我打赌甚至可以实现 30 或 40 倍的加速。

格雷码顺序的笛卡尔积：在此顺序中包括受影响的集合？

Cartesian product in Gray code order : including affected set in this order?

python

cartesian-product

gray-code

constant-time