笛卡尔产品的灰色代码顺序：包括受影响的集在这个顺序中？

Question

有一个很好的解决方案。用itertools在格雷代码顺序中的笛卡尔积？灰色代码顺序中的笛卡尔积的一个元素到下一个元素的变化，有没有办法在这个解决方案中添加一些简单的东西来报告这个集合（它的索引）？ 也就是说，一个 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)

我想避免在连续的图元组之间取 "差值"， 但要有恒定的时间更新 -- 所以才有了格雷代码顺序的事情。 一个解决方案是写一个 index_changed 迭代器。即, index_changed(3,2,2) 将返回序列 -1,2,1,2,0,2,1,2,0,2,1,2 我想要的，但是否可以在上面的解决方案中加入更简单的东西来达到同样的效果？

Answer 1

这个问题有好几个问题，但我还是保持这样，而不是把它变成一个 "变色龙问题"，只会让问题变得更糟

的确，既然有了这个 "索引改变 "的序列，为什么还要按格雷码顺序求笛卡尔积的元素呢？ 所以我想，我真正要找的是这个序列的高效计算。 所以我最终实现了上述的 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倍的速度。