В этом вопросе есть несколько неправильных вещей, но я буду держать его таким, а не только усугублять его, превращая его в «вопрос хамелеона»
Действительно, зачем даже спрашивать об элементах Декартово произведение в порядке кода Грея, когда у вас есть эта последовательность "индекс изменился"? Поэтому я полагаю, что я действительно искал эффективное вычисление этой последовательности. В итоге я реализовал вышеупомянутый gray_code_product_with_change, который принимает базовый набор наборов, например, , ['a','b','c'], [0,1], ['x','y'], вычислил эту последовательность «изменение индекса» и обновил этот базовый набор наборов по мере перемещается по последовательности. Поскольку реализация оказалась более интересной, чем я думал, я решил поделиться, если кто-то сочтет это полезным:
(Отказ от ответственности: вероятно, не самый pythoni c код, скорее почти 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, выполняя операции сдвига битов >>, et c. , так что я держу пари, что даже 30 или 40-кратное ускорение может быть достигнуто.