соответствие не обычные двоичные числа, а числа в коде Грея. Для кода Грея как раз и характерно то, что два соседних двоичных числа отличаются друг от друга не более чем на один разряд. Для генерирования последовательности чисел в коде Грея можно использовать следующий алгоритм (B – двоичное число и G – его код Грея):

–начнём с B=0 ;

–положим G [1]=B[1] ;

–G[i ]=B [i]xor B[i−1], 2≤i≤n .

Втаблице ниже приведено соответствие между обычными трёхразрядными двоичными числами и числами в коде Грея (D обозначает десятичное число):

Генерация размещений без повторений

Алгоритмы генерации размещений без повторений достаточно сложны и здесь не рассматриваются.

Генерация размещений с повторениями

Рассмотрим генерацию размещений с повторениями на примере множества X ={a ,b , c} :

(1,1),(1,2),(1,3)

(2,1),(2,2),(2,3) (3,1),(3,2),(3,3)

Неправда ли, знакомая картина? Для размещений по два и по три можно использовать вложенные циклы, а для большего количества элементов в размещении можно воспользоваться рекурсией.

Генерация сочетаний с повторениями

Аналогично рассмотрим генерацию сочетаний с повторениями на примере множества

X ={a ,b , c} :

(1,1),(1,2), (1,3)

(2,2),(2,3) (3,3)

Также часто встречающаяся последовательность. Для сочетаний по два можно использовать вложенные циклы, а в остальных случаях – рекурсию.

Генерация всех разбиений

Алгоритмы генерации всех разбиений сложны и потребуют отдельную лекцию, поэтому здесь не рассматриваются.