Коды Грея и задачи перебора

[SowingSadness]

Очень много формул. :( (4 утра, я не готов ещё вникать)
Хотелось бы в конце вывод. что нам дают коды Грея?

[demolishka]

Много формул потому что статья писалась преимущественно для хаба «Математика», но карма не позволила опубликовать статью в нем. Собственно здесь демонстрируется математический подход к составлению алгоритмов.

Коды Грея дают нам элегантное решение двух описанных в статье комбинаторных задач. Это естественно не главное их применение. Если верить Википедии, то

Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления.

Но это уже другая история.

[lightcaster]

Автор, не обижайтесь, но из-за такого изложения многие и не любят математику. Мне понравилось что вы последовательно расписали теоремы, и вам плюс за статью. Но плохо понятно их применение, и главное, зачем вы об этом пишите. Какие у вас мотивы? Если показать пример, как математически формулировать алгоритмы, то так и напишите. Хабр ж не лекториум, где профессор должен наболтать лекцию на 2, а студенты законспектировать.

За статью спасибо.

[demolishka]

Если бы вместо формул я пытался бы изложить все в виде текста и картинок — статья бы вышла размером раз в 10 больше, как и время затраченное на ее написание. Да, придется напрячься, чтобы разобраться в написанном — но это так и в любой математической литературе.
Что касается мотивов, то их несколько: показать математический подход к составлению алгоритмов, разобрать две полезные комбинаторные задачи, ну и чисто для себя — попрактиковаться в изложении материала.

[lightcaster]

Вы не поняли. Против формул я ничего не имею, и очень даже за. Вопрос в том, что я ранее не встречался с кодами Грея. Мне интересно, но абсолютно непонятно откуда это и как применить. Даже в математических текстах есть abstract, где дается контекст проблемы.

[demolishka]

Разве этот самый abstract не есть решение приведенных в статье задач? А те места, где эти задачи всплывают уже являются узко-направленными(ниже в комментариях есть примеры), также как и изначальное применение таких кодов Греем. Это уже темы для другой статьи или соответствующей литературы, с которой я, увы, не знаком. Как и большинство теории в математике — до поры до времени непонятно где ее использовать, поэтому каждый сам найдет для себя применение этим знаниям.

[hellman]

А по мне так наоборот, математические доказательства тут излишни. Важнее сама идея, алгоритм, примеры

[Harrix]

Коды Грея используются, например, еще для кодирования вещественных чисел в бинарных строках. И при этом малое изменение вещественного числа приведет к малому изменению бинарного числа. Это используется, например, в алгоритмах оптимизации.

[nckma]

код грея используется для повышения надежности аппаратуры, например, в устройствах-энкодерах или при передаче данных из одного клокового домена в другой (это когда данные фиксируются с частотой отличной от частоты на которой эти данные формируются: marsohod.org/index.php/ourblog/11-blog/190-meta1).

[devhashiops]

что нам дают коды Грея?

Про весь спектр применения кодов Грея не скажу, упомяну лишь частное.
При проектировании проектов на ПЛИС, например. Если создать большой счетчик на 20 триггерах, то при его инкрементировании обязательно возникают ситуации, когда сразу несколько триггеров меняют свое состояние:
255: 0_1111_1111 => 256: 1_0000_0000
при этом, триггеры переключаются в разное время и это очень плохо, стабильность такого счетчика оставляет желать лучшего и на больших частотах схема может работать неправильно.
Если же использовать коды Грея, то такой проблемы не будет, тк в соседних состояниях отличным может быть только один разряд. Те только один триггер переключится, что исключает так называемую «гонку сигналов».
Ну это простым языком)

[Mrrl]

Программу для k-элементных подмножеств заставить работать удалось, но с большим трудом. Там нужно если v=0, то вместо последних u элементов массива печатать нули, а если v=u — то единицы. И не забывать, что индексы в массиве нумеруются с 1, а не с 0! Иначе выводится непонятно что.
Работающая версия выглядит так:

int X[100],N;
void PrintX(int a,int b){
  for(int i=0;i<N;i++) printf("%d",i<a ? X[i] : b);
  printf("\n");
}
void Gray(int u,int v,int d){
	if(u==v) PrintX(N-u,1);
	else if(v==0) PrintX(N-u,0);
	else{
		X[N-u]=d;
		Gray(u-1,v-d,0);
		X[N-u]=1-d;
		Gray(u-1,v+d-1,1);
	}
}

[demolishka]

Я же написал справа от кода

Хотелось бы обратить внимание на то, что вывод двоичного кода подразумевает еще и заполнение оставшихся разрядов единицами или нулями, в зависимости от значения u и v.

тем самым предоставляя этот нюанс читателю.

[hellman]

А можно расширить до перебора всех подмножеств?

[Mrrl]

Как-то так:

void SGray(char *s,int n){
	for(char c='0';n;c='1'){
		*--s=c;
		SGray(s,--n);
		*s^=1;
	}
	puts(s);
}
void SGray(int n,char *buf){
	buf[n]=0;
	SGray(buf+n,n);
}

[Mrrl]

Кстати, есть ещё более простой способ генерации кодов Грея:

void Gray2(int n){
	for(int k=1<<n;--k>=0;){
		int s=k^(k>>1);
		for(int i=0;i<n;i++) printf("%d",(s>>i)&1);
		printf("\n");
	}
}

[hellman]

Если n <= 32 (или 64), можно использовать простую формулу (с вики):
gray(n) = n ^ (n >> 1)

[hellman]

n <= 32 это в смысле чтобы в регистр влезло. Если есть поддержка длинных чисел (например на Python), подойдет для любого n.

Правда, это формула для получения n-го члена последовательности, а не генерации всей последовательности.

[ZiroKyl]

В дополнение
Один из способов генерации 2D кода Грея (сигнального созвездия) для: QAM-4, QAM-16, QAM-64, QAM-256, ...

И если в университете вам показывали "метод зиг-зага", и вам было трудно его запомнить/понять/использовать, то этот способ будет более простым/наглядным/быстрым, чем "зиг-заг".

P.S. Возможно скоро кто-нибудь сделает видео получше (у меня плохо получаются real-time записи), и добавит в него QAM-64 и QAM-256. ...возможно.

[Pubert]

Многие спрашивают, где коды Грея применяются. Приведу простейший пример:

Задача скрейпинга отзывов с Амазона. Так как вывод ограничен всего 10-ю страницами, в ход идёт перебор фильтров. То есть мы просто поочередно перебираем все фильтры, затем уникьюлизируем результаты

Но вот проблема: при изменении одного фильтра страница перезагружается. При переборе фильтров в цикле получилось бы очень много лишних перезагрузок, т.к. за 1 итерацию мы меняем сразу несколько фильтров. Так как у меня в тот момент была гонка с другим программистом в этой задаче, я стал думать, как это оптимизировать. И придумал собственный "цикличный код Грея" (на тот момент я даже не знал о существовании такого). Я добился того, что на каждой итерации я изменяю ровно 1 фильтр, но перебираю все значения