2014-02-02
3548
Генерация всех последовательностей длины n из чисел 0,1…k-1 в лексикографическом порядке.
Генерация всех последовательностей длины n из нулей и единиц в лексикографическом порядке.
Определим лексикографический порядок на множестве последовательностей. Будем считать, что последовательность a предшествует последовательности b, если первые i членов у этих последовательностей одинаковы, а i+1 – й член у последовательности a меньше.
Последовательности из нулей и единиц можно считать двоичными числами. Тогда последовательность a предшествует b, если ее двоичное число меньше. Сгенерировать все n – разрядные двоичные числа очень просто. Нужно начать с числа 000…0 и прибавлять по единице до тех пор, пока не получим число 111…1. Для того, чтобы прибавить к двоичному числу единицу, необходимо перебирать цифры данного числа справа налево до тех пор, пока в каком-нибудь разряде не встретим 0. Затем этот разряд нужно сделать равным 1, а все разряды, лежащие справа от него, сделать нулями.
|
|
|
В качестве примера приведем программу, которая генерирует все последовательности из нулей и единиц длины 4.
#include<stdio.h>
#include<conio.h>
#define n 4
int x[n];
main(){
int i,k;
for(i=0;i<n;i++) // Формируем начальную последовательность.
x[i]=0;
while(1){
for(i=0;i<n;i++) // Печатаем очередную последовательность
printf(“%d “,x[i]);
printf(“\n”);
for(k=n-1;k>=0 && x[k]==1;k--) // Ищем первый справа ноль
x[k]=0; // Попутно единицы справа от первого нуля
//превращаем в нули
if(k==-1) break; // Если ни одного нуля не нашли,
// то все последовательности уже сгенерированы.
else x[k]=1; // Иначе на место найденного нуля ставим 1.
}
getch();
return 0;
}
Аналогично можно генерировать все последовательности длины n из чисел 0,1,…k-1. Начинаем с последовательности 000…0. Печатаем очередную последовательность. Строим по ней следующую. Для этого, двигаясь с конца последовательности, находим элемент, который меньше k-1. Увеличиваем его на 1, а все элементы, расположенные правее его, делаем нулями. Печатаем следующую последовательность и т.д. Процесс продолжается до тех пор, пока все элементы последовательности не станут равны k-1.
Упр. Видоизменить программу из предыдущего параграфа, чтобы она печатала всепоследовательности длины n из чисел 0,1…k-1.
Часто возникает необходимость генерировать все подмножества данного множества таким образом, чтобы следующее подмножество получалось из предыдущего добавлением или удалением одного элемента. В терминах характеристических последовательностей это означает, что каждая следующая характеристическая последовательность отличается от предыдущей в одном разряде. Набор всех последовательностей из нулей и единиц длины n, удовлетворяющих этому свойству, называется бинарным кодом Грея. Наиболее часто применяют рефлексивный бинарный код Грея.
|
|
|
Приведем рефлексивный бинарный код Грея для n=1,2,3.
| N=1 | n=2 | n=3 | ||||||
| № | Код Грея | у | № | Код Грея | у | № | Код Грея, | у |
| 2 | 001 | 1 | ||||||
| 3 | 011 | 0 | ||||||
| 4 | 010 | 2 | ||||||
| 5 | 110 | 0 | ||||||
| 6 | 111 | 1 | ||||||
| 7 | 101 | 0 | ||||||
| 8 | 100 |
Если отбросить старший разряд, станет понятно, почему данный код называется рефлексивным (т.е. отраженным). Дело в том, что вторая половина значений в оставшейся части кода Грея эквивалентна первой половине, только в обратном порядке. В примере для n=2 и n=3 первая и вторая половины выделены желтым и синим цветом. Если же разделить каждую половину ещё раз пополам, свойство будет сохраняться для каждой из половин половины и т. Д.
Будем начинать генерацию с последовательности 000…0. Для продолжения процесса генерации нам необходимо на каждом шаге знать номер разряда, который будет на этом шаге изменяться. Будем хранить эти номера в массиве y. Очевидно, что в массиве должно быть 2n – 1 элементов. Элемент yi будет обозначать номер разряда, который изменяется при переходе от i – той последовательности к следующей. В примере справа от кодов Грея записаны элементы массива y для n=1,2,3. Если мы знаем массив у кода Грея для i элементов, нетрудно получить значения элементов массива y для i+1- го элемента. Для этого нужно переписать старый массив y, затем записать в массив i, а затем снова переписать старый массив y. Это наблюдение позволяет написать несложную программу генерации кода Грея длины n.
#include<stdio.h>
#include<conio.h>
#define n 5
#define nn 32
int x[n], y[nn];
main(){
int i,j,k=1;
for(i=1;i<n;i++){ //Формируем массив y для i+1-го элемента
//Левая половина была сформирована на предыдущем шаге
y[k]=i; //В середину записываем i
for(j=0;j<k;j++) //Формируем правую половину
y[k+j+1]=y[j];
k=2*k+1;
}
for(i=0;i<n;i++) //Создаем начальную последовательность
x[i]=0;
for(i=0;i<=k;i++){
for(j=n-1;j>=0;j--) //Печатаем очередную последовательность
printf(“%d “,x[j]);
printf(“\n”);
x[y[i]]=1-x[y[i]]; //Изменяем в ней нужный разряд
}
getch();
return 0;
}
Если сравнить номера элементов последовательности кодов Грея и элементы массива y, можно заметить, что yi – это количество нулей, которыми заканчивается число i+1 в двоичной записи. Чтобы получить yi, нужно найти максимальную степень двойки, на которую делится i+1. Это позволяет написать следующую версию программы генерации кода Грея:
#include<stdio.h>
#include<conio.h>
#define n 5
int x[n];
main(){
int i,j,y,k=1,del;
for(i=0;i<n;i++){
x[i]=0; //Формируем начальную последовательность
k=k*2; //k=2n – количество последовательностей
}
for(i=0;i<k;i++){
for(j=n-1;j>=0;j--) //Печатаем очередную последовательность
printf(“%d “,x[j]);
printf(“\n”);
y=0; del=i+1; //Считаем максимальную степень двойки,
while(del%2==0){ //на которую делится i+1.
del/=2;
y++;
}
x[y]=1-x[y]; //Меняем нужный разряд
}
getch();
return 0;
}
